解析不同字符串的相等 XOR 值以进行字谜检测

Question

我最近有一个面试问题，我必须编写一个接受两个字符串的函数，1如果它们是彼此的字谜，它将返回，否则返回0。为简化起见，两个字符串的长度相同，非空，并且仅包含小写字母和数字字符。

我实现了一个函数，该函数独立地累加每个字符串的每个字符的 XOR 值，然后比较每个字符串的最终 XOR 值以查看它们是否相等。如果是，我会返回1，否则返回0。

我的功能：

int isAnagram(char* str1, char* str2){
    int xor_acc_1 = 0;
    int xor_acc_2 = 0;
    for(int i = 0; i<strlen(str1); i++){
        xor_acc_1 ^= str1[i] - '0';
        xor_acc_2 ^= str2[i] - '0';
    }
    return xor_acc_1 == xor_acc_2;
}

除了一个测试用例，我的函数适用于每个用例。

char* str1 = "123";
char* str2 = "303";

令我惊讶的是，尽管这两个字符串不是彼此的字谜，但它们都48作为 XOR 值返回。

我的问题是：通过修改 XOR 背后的数学，可以在线性时间内使用 XOR 解决这个问题，而不使用数据结构（例如 Map）？

Answer 1

纯粹的xor解决方案是行不通的，因为在此过程中会丢失信息（此问题也可能存在于其他形式的有损计算中，例如散列）。在这种情况下丢失的信息是用于比较的实际字符。

举例来说，考虑两个字符串ae和bf（在 ASCII 中）：

  a: 0110 0001    b: 0110 0010
  e: 0110 0101    f: 0110 0110
     ---- ----       ---- ----
xor: 0000 0100       0000 0100

您可以看到xor两个字符串的结果相同，尽管它们完全不同。

一旦您意识到任何值-ed 本身为零，这可能会变得更加明显xor，这意味着所有像aa, bb, cc,等的字符串xx在您的方案下都将被视为字谜。

因此，现在您已经确定该方法不合适，您会想到几个选项。

第一种是简单地对两个字符串进行排序并比较它们。排序后，它们将在逐个字符的基础上相同。这会起作用，但不太可能满足您要求的O(n)时间复杂度，因为您几乎肯定会使用比较样式排序。

第二个仍然允许您通过使用通常的时间交易空间“技巧”来满足该要求。您只需设置每个字符的计数（最初全部为零），然后，对于第一个字符串中的每个字符，增加其计数。

之后，对于第二个字符串中的每个字符，减少其计数。

这是线性时间复杂度，如果处理后每个字符计数都设置为零，则字符串可以被视为字谜。只有当一个字符在一个字符串中出现的次数多于另一个时，才会出现任何非零计数。

这实际上是一种计数排序，一种非比较排序，这意味着它不受O(n log n)这些排序的正常最小时间复杂度的约束。

这种野兽的伪代码是：

def isAnagram(str1, str2):
    if len(str1) != len(str2):    # Can also handle different lengths.
        return false

    dim count[0..255] = {0}       # Init all counts to zero.

    for each code in str1:        # Increase for each char in string 1.
        count[code]++

    for each code in str2:        # Decrease for each char in string 2.
        count[code]--

    for each code in 0..255:
        if count[code] != 0:      # Any non-zero means non-anagram.
            return false    

    return true                   # All zero means anagram.

顺便说一下，这里是一个完整的 C 测试程序，它说明了这个概念，能够处理 8 位字符宽度，尽管可以通过对该#if部分进行简单的更改来添加更多宽度：

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

#if CHAR_BIT == 8
    #define ARRSZ 256
#else
    #error Need to adjust for unexpected CHAR_BIT.
#endif

static bool isAnagram(unsigned char *str1, unsigned char *str2) {
    // Ensure strings are same size.

    size_t len = strlen(str1);
    if (len != strlen(str2))
        return false;

    // Initialise all counts to zero.

    int count[ARRSZ];
    for (size_t i = 0; i < sizeof(count) / sizeof(*count); ++i)
        count[i] = 0;

    // Increment for string 1, decrement for string 2.

    for (size_t i = 0; i < len; ++i) {
        count[str1[i]]++;
        count[str2[i]]--;
    }

    // Any count non-zero means non-anagram.

    for (size_t i = 0; i < sizeof(count) / sizeof(*count); ++i)
        if (count[i] != 0)
            return false;

    // All counts zero means anagram.

    return true;
}

int main(int argc, char *argv[]) {
    if ((argc - 1) % 2 != 0) {
        puts("Usage: check_anagrams [<string1> <string2>] ...");
        return 1;
    }

    for (size_t i = 1; i < argc; i += 2) {
        printf("%s: '%s' '%s'\n",
            isAnagram(argv[i], argv[i + 1]) ? "Yes" : " No",
            argv[i], argv[i + 1]);
    }

    return 0;
}

在一些合适的测试数据上运行它显示了它的作用：

pax$ ./check_anagrams ' paxdiablo ' 'a plaid box' paxdiablo PaxDiablo \
         one two aa bb aa aa '' '' paxdiablo pax.diablo

Yes: ' paxdiablo ' 'a plaid box'
 No: 'paxdiablo' 'PaxDiablo'
 No: 'one' 'two'
 No: 'aa' 'bb'
Yes: 'aa' 'aa'
Yes: '' ''
 No: 'paxdiablo' 'pax.diablo'