寻找字谜

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

首先，这不是正确的解决方案。想想这 2 个字符串："aabc" 和 "aade" a[0] == b[0]、a[0] == b[1]、a[1] == b[0] 和 a[1] == b[1]。 len 将是 4，但它们不是字谜。复杂度为 O(n^2)，即字符串的长度为 n。

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

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

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

Answer 2

最佳解决方案可能基于计算每个字符串中的字符数，然后比较两个计数。理想情况下，我们应该使用 Dictionary 数据结构，但为了简单起见，我将在数组上演示该算法：

char *word1 = "word1";
char *word2 = "ordw1";

// C strings can have only 256 possible characters, therefore let's store counts in an array with 256 items.
int* letterCounts1 = calloc(256, sizeof(int));
int* letterCounts2 = calloc(256, sizeof(int));
size_t length1 = strlen(word1);
size_t length2 = strlen(word2);

for (size_t i = 0; i < length1; i++) {
    int letterIndex = word1[i] & 0xFF;
    letterCounts1[letterIndex] += 1;
}

for (size_t i = 0; i < length2; i++) {
    int letterIndex = word2[i] & 0xFF;
    letterCounts2[letterIndex] += 1;
}

bool isAnagram = true;

for (size_t i = 0; i < 256; i++) {
    if (letterCounts1[i] != letterCounts2[i]) {
        isAnagram = false;
        break;
    }
}

free(letterCounts1);
free(letterCounts2);

if (isAnagram) {
    printf("Anagram");
} else {
    printf("Not anagram");
}

该算法具有线性 (O(n)) 复杂度（迭代 "dictionary" 可以被认为是一个常数）。

您的原始解决方案具有二次复杂性，但是，您还必须确保将 strlen 的结果存储到变量中，因为每次调用 strlen 都必须遍历整个字符串，增加复杂度到立方。

Answer 3

这里有一些答案：

您的算法不处理重复字母，它可能 return 误报。
不清楚是否正确，因为你没有post一个包含所有声明和定义的完整函数定义，尤其是len是否初始化为0。
它有O(N²)时间复杂度甚至O(N³) 如果编译器无法优化对 strlen().

对于具有线性复杂度的 8 位字符的系统，这是一个简单的解决方案：

#include <stdio.h>
#include <string.h>

int check_anagrams(const char *a, const char *b) {
    size_t counters[256];
    size_t len = strlen(a);
    size_t i;

    if (len != strlen(b)) {
        printf("Not anagrams\n");
        return 0;
    }
    for (i = 0; i < 256; i++) {
        counters[i] = 0;
    }
    for (i = 0; i < len; i++) {
        int c = (unsigned char)a[i];
        counters[c] += 1;
    }
    for (i = 0; i < len; i++) {
        int c = (unsigned char)b[i];
        if (counters[c] == 0) {
            printf("Not anagrams\n");
            return 0;
        }
        counters[c] -= 1;
    }
    printf("Anagrams\n");
    return 1;
}

寻找字谜

Finding anagram

c

string

anagram