查找anagram

Question

if (strlen(a) != strlen(b)) {
    printf("Not anagram");
} else {
    for (int i = 0; i < strlen(a); i++) {
        for (int j = 0; j < strlen(b); j++) {
            if (a[i] == b[j]) {
                len++;
            }
        }
    }
    if (len != strlen(a))
        printf("Not anagram");
    else
        printf("Anagram");
}
return 0;

这是一个代码片段，用于检查2个字符串是否为字形。这里如何处理重复字符？另外，这个程序可以做得更优化吗？这段代码的运行时复杂度是多少？

Answer 1

首先，这不是正确的解决方案。想想这两个字符串："aabc“和"aade”a == b，a == b1，a1 == b和a1 == b1。len应该是4，但它们不是变形词。复杂度为O(n^2)是字符串长度的n。

正如@Sulthan回答的那样，更好的方法是对复杂度为O(n*log(n))的字符串进行排序，然后一次性比较两个字符串O(n)。

要对O(n * log(n))中的字符串进行排序，不能使用冒泡方法，但可以使用合并排序，如下所述：https://www.geeksforgeeks.org/merge-sort/

更好的方法是创建一个整数数组，计算第一个字符串中每个字符的出现次数，然后减去第二个数组中每个字符出现的次数。最后，辅助数组的所有位置都必须为0。