242 有效的字母异位词
Solution
暴力解法(超时)
class Solution {
public:
bool judge(string s, string t) {
// 默认s.size() > t.size()
vector<bool> isVisited(t.size(), false);
for (int i = 0; i < s.size(); i++) {
bool find = false;
for (int j = 0; j < t.size(); j++) {
if (!isVisited[j] && s[i] == t[j]) {
isVisited[j] = true;
find = true;
break;
}
}
if (!find)
return false;
}
return true;
}
bool isAnagram(string s, string t) {
if (s.size() > t.size())
return judge(s, t);
else
return judge(t, s);
}
};
复杂度分析
- 时间复杂度:\(O(n^2)\)
- 空间复杂度:\(O(n)\)
哈希表
题目说了“s 和 t 仅包含小写字母”,因此哈希表key只有26个,并且是连续的,数组就可以满足。
计数思想:s出现的字符加1,t出现的字符减1,如果最后计数器不为0,则说明s字符和t字符不匹配
class Solution {
public:
bool isAnagram(string s, string t) {
int hashMap[26] = {0};
for(char c : s){
hashMap[c - 'a']++;
}
for(char c : t){
hashMap[c - 'a']--;
}
for(int i : hashMap){
if(i != 0)
return false;
}
return true;
}
};
复杂度分析:
- 时间复杂度: \(O(n)\)
- 空间复杂度: \(O(n)\)