題目:
給定兩個字符串 s 和 t ,編寫一個函數(shù)來判斷 t 是否是 s 的字母異位詞。
注意:若s 和 t中每個字符出現(xiàn)的次數(shù)都相同,則稱s 和 t互為字母異位詞。
示例1:
輸入: s = "anagram", t = "nagaram"
輸出: true
示例 2:
輸入: s = "rat", t = "car"
輸出: false
提示:
1 <= s.length, t.length <= 5 * 104
s 和 t僅包含小寫字母
來源:力扣(LeetCode)
鏈接:https://leetcode.cn/problems/valid-anagram
創(chuàng)新互聯(lián)專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務,包含不限于成都網(wǎng)站制作、做網(wǎng)站、德欽網(wǎng)絡(luò)推廣、小程序開發(fā)、德欽網(wǎng)絡(luò)營銷、德欽企業(yè)策劃、德欽品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運營等,從售前售中售后,我們都將竭誠為您服務,您的肯定,是我們最大的嘉獎;創(chuàng)新互聯(lián)為所有大學生創(chuàng)業(yè)者提供德欽建站搭建服務,24小時服務熱線:13518219792,官方網(wǎng)址:www.cdcxhl.com
對于這樣的題,解題思路是:
在s中尋找構(gòu)成t的每個字符是否存在
1.特殊情況:如果兩者不相等,那么就不可能互為異位詞
2.通常情況:如果兩者相等,就需要對S中每個元素在t中尋找
假如S中有n個元素,t中有n個元素,那么就需要n*n次查找。(暴力的直接找)
對于這種的需要查找匹配的我可以考慮使用map,C++中STL的map是使用樹來做查找算法的。
原因:
1)用A B C等作為index不好進行查找。
2)順序查找比較慢,效率低。
為了解決 1)
我們可以用數(shù)組解決----把字符轉(zhuǎn)為數(shù)組下標作為index
(原理是:通過一個函數(shù)(字符-‘a(chǎn)’)就轉(zhuǎn)為index)
這樣的話其實和我們的哈希就對應上了,所以說數(shù)組就是一個簡單的哈希表。
bool isok(string s, string t) {
int ha[26]={0};
for(int i=0;i
2.map的解法
()
bool isok(string s, string t) {
if(s.size() != t.size()) return false;
map MAP;
for(int i = 0; i
};
對第二種解法的補充:
首先我們介紹一下兩種編碼 **
1.最開始的ASCII--對應了英語字符和二進制的關(guān)系
2.后來為了改進,將世界上所有的字符都給包含進去的Unicode**
通過這樣的介紹,可以知道如果按照第一種解法來做,那么局限性就很大了,編碼的不足夠,雖然在這種簡單的題上,數(shù)組模擬(4ms)確實更快(map 20ms),但是不是通用,所以按需選擇吧。