时间戳

首页 > 解决方案 > 寻找字谜

c - 寻找字谜

问题描述

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 个字符串是否是字谜。这里如何处理重复字符？另外，这个程序可以更优化吗？这段代码的运行时复杂度是多少？

标签： cstringanagram

解决方案

最佳解决方案可能是基于计算每个字符串中的字符数，然后比较两个计数。理想情况下，我们应该使用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)) 复杂性（对“字典”的迭代可以被认为是一个常数）。

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

推荐阅读