我最近有一个面试问题，我必须编写一个接受两个字符串的函数，如果它们是彼此的字谜，它将返回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解决方案将不起作用，因为在此过程中会丢失信息(此问题也可能存在于其他形式的有损计算中，例如散列(。在这种情况下丢失的信息是用于比较的实际字符。
例如，考虑两个字符串ae和bf(ASCII(：
a: 0110 0001 b: 0110 0010
e: 0110 0101 f: 0110 0110
---- ---- ---- ----
xor: 0000 0100 0000 0100
您可以看到，尽管两个字符串完全不同，但两个字符串的xor结果是相同的。
一旦你意识到任何与自身xor-ed 的值都是零，这意味着所有字符串如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'
为什么首先需要执行 XOR？
最简单和最快速的方法是按字符对字符串进行排序，并比较它们是否相等。在这种情况下，如果需要更快的排序算法，可以使用计数排序来实现线性时间。
另一种方法是，您可以简单地计算每个字符串中的字符数并检查这些计数是否相等。
编辑
您的基于异或的解决方案在正确性方面是不正确的。可以有多个字符组合可以XOR到相同的数字，两个不同字符串的字符/ASCII代码的XOR可能不会一直产生不同的XOR。因此，对于相同的字符串，输出将始终正确。但是对于不同的字符串，输出可能并不总是正确的(误报(。