242. Valid Anagram
Given two strings s and t, write a function to determine if t is an anagram of s.
For example, s = “anagram”, t = “nagaram”, return true. s = “rat”, t = “car”, return false.
Note: You may assume the string contains only lowercase alphabets.
非常经典的变位词问题，此题降低了难度，因为只要求判断小写字母组成的变位词，那么方法无外乎就是sort和hash-table。
通过观察，我们发现互为变位词的两个词中每个字母出现次数一定是相同的，所以最基本的思路是用两个哈希表来存字母和次数的键值对，代码如下:
/*solution 1,52ms*/
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.empty()&&t.empty())
return true;
if(s.size()!=t.size())
return false;
unordered_map<char,int> hash;
unordered_map<char,int> hash2;
bool flag=false;
for(int i=0;i<s.size();i++)
hash[s[i]]++;
for(int i=0;i<t.size();i++)
hash2[t[i]]++;
for(int i=0;i<s.size();i++){
if(hash[s[i]]==hash2[s[i]])
flag=true;
else
return false;
}
return flag;
}
};
最初的代码不是很好，因为对于两个空字符串的情况需要单独进行判断，运行时间较长，而且用了两个哈希表，不够优雅，所以我开始考虑如何优化。
既然每个字母出现次数相同，那么我们可以只用一个哈希表:
- 当s中的字母被储存在哈希表中时，其对应的值+1;
- 当t中的字母被储存在哈希表中时，其对应的值-1;
代码如下:
/*solution2 36ms*/
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size()!=t.size())
return false;
unordered_map<char,int> hash;
for(int i=0;i<s.size();i++){
hash[s[i]]++;
hash[t[i]]--;
}
for(auto pos:hash)
if(pos.second!=0)
return false;
return true;
}
};
这次只用了36ms，减少一个哈希表的使用可以换来效率上的很大的提升，那么，还能不能继续优化呢？
我们知道，哈希表的作用在于完成以O(1)为时间复杂度的查找操作，不过这道题中我们更多的是在使用哈希表中的键值对关系，而不是需要频繁的查找操作，所以，针对这道题，我们可以用一个数组来替换掉哈希表，代码如下:
/*solution 3,use array instead of hash-table,12ms*/
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size()!=t.size())
return false;
int count[26]={0};
for(int i=0;i<s.size();i++){
count[s[i]-'a']++;
count[t[i]-'a']--;
}
for(int pos:count)
if(pos!=0)
return false;
return true;
}
};
只用了12ms，效率已经比较高了。
当然，最简单的方法就是排序后进行比较，非常简单，不再赘述了。