題目：
給定兩個字串 s 和 t ，撰寫一個函式來判斷 t 是否是 s 的字母異位詞，
注意：若 s 和 t 中每個字符出現的次數都相同，則稱 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
對于這樣的題，解題思路是：
在s中尋找構成t的每個字符是否存在
1.特殊情況：如果兩者不相等，那么就不可能互為異位詞
2.通常情況：如果兩者相等，就需要對S中每個元素在t中尋找
假如S中有n個元素，t中有n個元素，那么就需要n*n次查找，（暴力的直接找）
對于這種的需要查找匹配的我可以考慮使用map,C++中STL的map是使用樹來做查找演算法的，
原因：
1）用A B C等作為index不好進行查找，
2）順序查找比較慢，效率低，
為了解決 1）
我們可以用陣列解決----把字符轉為陣列下標作為index
（原理是：通過一個函式（字符-‘a’）就轉為index）
這樣的話其實和我們的哈希就對應上了，所以說陣列就是一個簡單的哈希表，
bool isok(string s, string t) {
int ha[26]={0};
for(int i=0;i<s.size();i++)
ha[s[i]-'a']++;
for(int j=0;j<t.size();j++)
ha[t[j]-'a']--;
for(int i=0;i<26;i++)
if(ha[i]!=0)
return false;
return true;
}//這個相對于暴力解法O(n*n)來說，時間復雜度只有O(n)
2.map的解法
（）
bool isok(string s, string t) {
if(s.size() != t.size()) return false;
map<char,int> MAP;
for(int i = 0; i<s.size(); i++){
MAP[s[i]] ++;
}
for(int i = 0; i<t.size(); i++){
MAP[t[i]] --;
if(MAP[t[i]] < 0) return false;
}
return true;
}
};
對第二種解法的補充：
首先我們介紹一下兩種編碼 **
1.最開始的ASCII--對應了英語字符和二進制的關系
2.后來為了改進，將世界上所有的字符都給包含進去的Unicode**
通過這樣的介紹，可以知道如果按照第一種解法來做，那么局限性就很大了，編碼的不足夠，雖然在這種簡單的題上，陣列模擬（4ms）確實更快（map 20ms），但是不是通用，所以按需選擇吧，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/510826.html
標籤：C++