Given two strings s and t , write a function to determine if t is an anagram of s.
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
Note:
You may assume the string contains only lowercase alphabets.
Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?
我的答案：hash table （multiset慢好几倍）
class Solution {
public:
bool isAnagram(string s, string t) {
int len_s = s.size();
int len_t = t.size();
if (len_s != len_t)
return false;
unordered_map<char, int> map_s;
unordered_map<char, int> map_t;
for (int i=0; i<len_s; ++i) {
char c_s = s[i];
char c_t = t[i];
if (map_s.find(c_s) == map_s.end())
map_s[c_s] = 1;
else
++map_s[c_s];
if (map_t.find(c_t) == map_t.end())
map_t[c_t] = 1;
else
++map_t[c_t];
}
for (const auto& p_s : map_s) {
if ( p_s.second != map_t[p_s.first] ) {
return false;
}
}
return true;
}
};
Runtime: 28 ms, faster than 44.13% of C++ online submissions for Valid Anagram.
Memory Usage: 7.7 MB, less than 22.42% of C++ online submissions for Valid Anagram.
看答案：
https://leetcode.com/problems/valid-anagram/solution/
确实用hash table比较快，但是这边不用2个hash table，只用一个，然后加减就可以了，想到229这道题
https://leetcode.com/problems/majority-element-ii/discuss/63520/Boyer-Moore-Majority-Vote-algorithm-and-my-elaboration
Boyer-Moore Majority Vote algorithm
