题目

Write a method to decide if two strings are anagrams or not.

写一个函数判断两个字符串是否是变位词。

解答

变位词(anagrams)指的是组成两个单词的字符相同，但位置不同的单词。

比如说， abbcd和abcdb就是一对变位词。
也就是说，2个字符串，不管排列顺序如何，只要全部的单个字符能对应上，就是一对变位词！

该题目有两种做法：

时间复杂度为O(nlogn)的解法

由于组成变位词的字符是一模一样的，所以按照字典序排序后，两个字符串也就相等了。 因此我们可以用O(nlogn)的时间去排序，然后用O(n)的时间比较它们是否相等即可。

代码如下：

//需要头文件#include<algorithm>

bool isAnagram1(string s, string t){ if(s=="" || t=="") return false; if(s.length() != t.length()) return false; //sort(s,s+s.length);//如果s是字符数组，就这样调用 sort(&s[0], &s[0]+s.length()); sort(&t[0], &t[0]+t.length()); if(s == t) return true; else return false;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

时间复杂度为O(n)的解法

由于组成变位词的字符是一模一样的， 因此我们可以先统计每个字符串中各个字符出现的次数， 然后看这两个字符串中各字符出现次数是否一样。如果是，则它们是一对变位词。 这需要开一个辅助数组来保存各字符的出现次数。我们可以开一个大小是256的整数数组(ascii码范围内的字符)， 遍历第一个字符串时，将相应字符出现的次数加1；遍历第二个字符串时， 将相应字符出现的次数减1。最后如果数组中256个数都为0，说明两个字符串是一对变位词。 (第1个字符串中出现的字符都被第2个字符串出现的字符抵消了)， 如果数组中有一个不为0，说明它们不是一对变位词。

代码如下：

//必须有头文件：#include <cstring>

bool isAnagram2(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;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

全部代码：

#include <iostream>
#include <algorithm>//用sort函数必须加的头文件
#include <cstring>
using namespace std;

bool isAnagram1(string s, string t){ if(s=="" || t=="") return false; if(s.length() != t.length()) return false; //sort(s,s+s.length);//如果s是字符数组，就这样调用 sort(&s[0], &s[0]+s.length()); sort(&t[0], &t[0]+t.length()); if(s == t) return true; else return false;
}

bool isAnagram2(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;
}

int main()
{ string s="asdfghj"; string t="jhgfdsa"; bool bo = isAnagram1(s,t); cout<<bo<<endl;//输出结果为1 s="asdfghj"; t="jhgfdss"; bo = isAnagram1(s,t); cout<<bo<<endl;//输出结果为0 s="asdfghj"; t="jhgfdsa"; bo = isAnagram2(s,t); cout<<bo<<endl;//输出结果为1 s="asdfghj"; t="jhgfdss"; bo = isAnagram2(s,t); cout<<bo<<endl;//输出结果为0 return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
 

文章来源: chenhx.blog.csdn.net，作者：谙忆，版权归原作者所有，如需转载，请联系作者。

原文链接：chenhx.blog.csdn.net/article/details/52005100