题目
原文：
Write a method to decide if two strings are anagrams or not.
译文：
写一个函数判断两个字符串是否是变位词。
解答
变位词(anagrams)指的是组成两个单词的字符相同，但位置不同的单词。比如说， abbcd和abcdb就是一对变位词。该题目有两种做法：
O(nlogn)的解法
由于组成变位词的字符是一模一样的，所以按照字典序排序后，两个字符串也就相等了。 因此我们可以用O(nlogn)的时间去排序，然后用O(n)的时间比较它们是否相等即可。
代码如下：
1
2
3
4
5
6
7
8
9
bool isAnagram1(string s, string t){
if(s=="" || t=="") return false;
if(s.length() != t.length()) return false;
sort(&s[0], &s[0]+s.length());
sort(&t[0], &t[0]+t.length());
if(s == t) return true;
else return false;
}
O(n)的解法
由于组成变位词的字符是一模一样的， 因此我们可以先统计每个字符串中各个字符出现的次数， 然后看这两个字符串中各字符出现次数是否一样。如果是，则它们是一对变位词。 这需要开一个辅助数组来保存各字符的出现次数。我们可以开一个大小是256的整数数组， 遍历第一个字符串时，将相应字符出现的次数加1；遍历第二个字符串时， 将相应字符出现的次数减1。最后如果数组中256个数都为0，说明两个字符串是一对变位词。 (第1个字符串中出现的字符都被第2个字符串出现的字符抵消了)， 如果数组中有一个不为0，说明它们不是一对变位词。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isAnagram(string s, string t){
if(s=="" || t=="") return false;
if(s.length() != t.length()) return false;
int len = s.length();
int c[256];
memset(c, 0, sizeof(c));
for(int i=0; i<len; ++i){
++c[(int)s[i]];
--c[(int)t[i]];
}
for(int i=0; i<256; ++i)
if(c[i] != 0)
return false;
return true;
}
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2012/12/06/1.4/
