c++ - 查找字符串是否是变位词 - 重访

Question

我确信这个问题在很久以前就已经在 Stack Overflow 上讨论过几次了。我只是想验证我的答案是否有效。我在这个thread看到这个问题.很抱歉，这篇文章与主题重复，如果必须删除它，我会这样做。

---

我想到了一种更简单的方法。通过对字符串中的字符进行异或运算。

所以 O(n) 用于对每个字符进行异或，O(1) 用于比较两个字符串中的最后一个字符，这给出了 O(n) 的解决方案。

即使最后一个字符可能是任何特殊符号，但如果字符串是变位词，它们最终还是相同的。我的逻辑对吗？

那么可以采用这种解决方案而不是进行所有排序和散列吗？我的代码是这样的:

char a[7] = "Length";
char b[7] = "enghtL";

for (int i = 1; i < 6; i++) {
   a[i] = a[i] ^ a[i-1];
   b[i] = b[i] ^ b[i-1];
}

if (a[5] == b[5]) {
   cout << "\n The strings are anagrams";
}
else {
   cout << "\n No they are not";
}

Answer 1

很抱歉，这行不通。

当然，如果它是一个字谜，代码(如果它工作正常)会这样说，但你也会有很多“误报”，因为几个(不同的)字符串可以产生相同的输出。