[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);}

作者：Viidiot 微信公众号：linux-code