[google面试CTCI] 1-4.判断两个字符串是否由相同字符组成


		【字符串与数组】
 
Q：Write a method to decide if two strings are anagrams or not
 
题目：写一个算法来判断两个字符串是否为换位字符串。（换位字符串是指组成字符串的字符相同，但位置不同）
 
解答： 
 
 
方法一：假设为ascii2码字符串，那么可以分配两个256大小的int数组，每个数组用于统计一个字符串各个字符出现的次数，最后，比较这两个int数组，看是否每个元素都相同。时间复杂度为O(n)。
 
int anagrams1(char* str1,char* str2){
int len1=strlen(str1);
int len2=strlen(str2);
if(len1 != len2)
return 0;
int flags1[256],flags2[256];
memset(flags1,0,sizeof(flags1));
memset(flags2,0,sizeof(flags2));
int i;
for(i=0;i<len1;++i){
++flags1[(int)str1[i]];
++flags2[(int)str2[i]];
}
for(i=0;i<256;++i){
if(flags1[i]!=flags2[i])
return 0;
}
return 1;
}
方法二：事实上可以在方法一的基础上更进一步简化，只需要分配一个256大小的int数组即可，某个字符在str1中出现，则将int数组对应元素值加1；某个字符在str2中出现，则将int数组对应元素值减去1，最后，只需要看int数组是否全为0。是不是更优雅？呵呵
 
int anagrams2(char* str1,char* str2){
int len1=strlen(str1);
int len2=strlen(str2);
if(len1 != len2)
return 0;
int flags[256];
memset(flags,0,sizeof(flags));
int i;
for(i=0;i<len1;++i){
++flags[str1[i]];
--flags[str2[i]];
}
for(i=0;i<256;++i){
if(flags[i]!=0)
return 0;
}
return 1;
}
方法三：不管三七二十一，我们把两个字符串排序。对排好序后的字符串进行比较。时间复杂度为O(n*logn)。
 
int anagrams(char* str1,char* str2){
return sort(str1)==sort(str2);
}

补充：综合编程 , 其他综合 ,