【题目】
原文:
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; }
时间: 2024-11-15 09:36:40