寻找字符串是否为变位词 - 重新审视

Question

我相信在Stack Overflow上已经有多次讨论过这个问题。我只是想验证一下我的答案是否正确。我在这个帖子中看到了这个问题。如果这篇文章是重复的，需要删除，我会马上删掉。

---

我想用一种更简单的方法来解决这个问题。只需将字符串中的字符进行异或运算即可。

因此，对于每个字符进行异或的时间复杂度为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";
}

- Ajai

---

根据您的程序，“ab”是“ef”的一个字谜。恐怕这种方法不可能奏效。 - TonyK

所以，基本上，“对于所有的a、b、c、d，是否成立 ((a XOR b XOR c) ≡ (c XOR a XOR b) ≡ (b XOR c XOR a) ≡ (c XOR b XOR a)) ∧ ((a XOR b) ≠ (a XOR d))，以及在元数的一般化中是否成立？” 我认为不是。 - Lightness Races in Orbit

@TonyK：哇！+1。没想到这个。 - Ajai

当我需要查找变位词时，我只是对单词中的字母进行排序并检查结果是否相同。 - visitor

Answer 1

抱歉，这个无法运行。

如果这是一个变形词，代码（如果正确运行）会提示它是变形词，但你可能会得到很多“假阳性”，因为几个不同的字符串可能会产生相同的输出。

- Valmond

---

"必要但不充分" - MSalters

Answer 2

你正在将一个n字节字符串的所有信息压缩成一个单字节 - 实际上是一个非常基本的哈希。每当两个不是变位词的字符串发生哈希冲突时，你将返回一个错误的结果。

如果你想要一个O(n)的方法来查找变位词，可以使用计数排序对单词进行排序，然后比较结果是否相等。

- JoeG

Answer 3

这段代码可能作为解决方案的一部分很有用。

我的方法是：

检查两个单词是否具有相同数量的字母，如果不是，则不能成为变位词。 然后将每个单词的字母排序为按字母顺序（或任何其他顺序） 遍历单词列表，并在字母不相等时返回false。

- Stefan

Answer 4

在C++中，您可以使用字符串反向迭代器：

std::string s1 = "Length";
std::string s2 = "htgneL";
std::string s3 = "htgnel";

if (s1 == std::string(s2.rbegin(), s2.rend()))
    std::cout << "s1 and s2 are anagram" << std::endl;
else
    std::cout << "s1 and s2 aren't anagram" << std::endl;

if (s1 == std::string(s3.rbegin(), s3.rend()))
    std::cout << "s1 and s3 are anagram" << std::endl;
else
    std::cout << "s1 and s3 aren't anagram" << std::endl;

- Tio Pepe

---

那只适用于反转字符串，而这只是众多可能的字谜之一。 - Lightness Races in Orbit

@TomalakGeret'kal，你是对的，我混淆了回文的定义。 - Tio Pepe