c - 有效地检查字谜？

Question

检查 2 个字符串（由 const char * 表示）是否是字谜的最有效方法是什么？我知道我们可以排序然后比较。但是，排序是 nlogn。

谢谢您的帮助。

编辑：我因为没有展示我的尝试而投了反对票。所以，我的尝试如下：

int anagram(const char * c1, const char *c2){
 char *s1=my_sort(c1);
 char *s2=my_sort(c2);
 return strcmp(s1,s2)==0?1:0;
}

Answer 1

它来自我的一篇博文：）

/**
* Works for 0-127 ASCII string
**/
int isanagram(const char* s1,const char* s2){
    int hash[128];
    int i;
    for(i=0;i<128;i++)
        hash[i]=0;
    while(*s1) hash[*s1++]++;
    while(*s2) hash[*s2++]--;
    for(i=0;i<128;i++)
        if(hash[i]) return 0;
    return 1;
}

解释：字母表中的每个字符在哈希表中都有一个位置。对于 s1 中的每个 char，我们增加该 char 的计数，对于 s2 中的每个 char，我们减少哈希表中 char 的计数。如果所有字符最后的计数为 0，则 s1 和 s2 的每个字符的数量相同，这就是 anagram 的定义。

复杂度： O(n) 如果 n>128 ，其中 n 是 s1 和 s2 长度的最大值