【题目】
原文：
1.4 Write a method to decide if two strings are anagrams or not.
译文：
写一个函数判断两个字符串是否是变位词。
【分析】
变位词(anagrams)指的是组成两个单词的字符相同，但位置不同的单词。比如说， abbcd和abcdb就是一对变位词。该题目有两种思路：
【思路一】
由于变位词只是字母的顺序改变，字符长度，字符种类没有改变，所以根据此我们只要重新根据字典序排序一下，两个字符串也就一样了。
The eyes（眼睛）——They see.（它们看得见。）这是一对变位词。
根据字典序排序他们都会变成：eeehtsy
时间复杂度为：O（nlogn）
【思路二】
由于组成变位词的字符是一模一样的， 因此我们可以先统计每个字符串中各个字符出现的次数， 然后看这两个字符串中各字符出现次数是否一样。如果是，则它们是一对变位词。 这需要开一个辅助数组来保存各字符的出现次数。我们可以开一个大小是256的整数数组， 遍历第一个字符串时，将相应字符出现的次数加1；遍历第二个字符串时， 将相应字符出现的次数减1。最后如果数组中256个数都为0，说明两个字符串是一对变位词。 (第1个字符串中出现的字符都被第2个字符串出现的字符抵消了)， 如果数组中有一个不为0，说明它们不是一对变位词。
【代码一】
/*********************************
* 日期：2014-05-06
* 作者：SJF0115
* 题目: 判断字符串是否为变位词
* 来源：CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
//判断字符串是否为变位词
bool IsAnagrams(string str1,string str2){
if(str1 == "" || str2 == ""){
return false;
}
int len1 = str1.length();
int len2 = str2.length();
//变位词长度一样
if(len1 != len2){
return false;
}
//排序
sort(&str1[0],&str1[0]+len1);
sort(&str2[0],&str2[0]+len2);
if(str1 == str2){
return true;
}
else{
return false;
}
}
int main(){
char str1[] = "the eyes";
char str2[] = "they see";
bool result = IsAnagrams(str1,str2);
cout<<result<<endl;
return 0;
}
【代码二】
//判断字符串是否为变位词
bool IsAnagrams(string str1,string str2){
int i;
if(str1 == "" || str2 == ""){
return false;
}
int len1 = str1.length();
int len2 = str2.length();
//变位词长度一样
if(len1 != len2){
return false;
}
//初始化
int vis[256];
memset(vis,0,sizeof(vis));
//遍历第一个字符串，将相应字符出现的次数加1
//遍历第二个字符串，将相应字符出现的次数减1
for(i = 0;i < len1;i++){
vis[str1[i]] ++;
vis[str2[i]] --;
}
//判断是否为变位词 如果数组中256个数都为0，说明两个字符串是一对变位词。
for(i = 0;i < 256;i++){
if(vis[i] != 0){
return false;
}
}
return true;
}
