有趣的是，有时最好的问题是最简单的。
这里的问题是如何推断两个词是否是字谜——一个词本质上是一个未排序的多字符集。
我们知道我们必须排序，但理想情况下我们希望避免排序的时间复杂性。
事实证明，在许多情况下，我们可以通过遍历它们并将字符值异或到累加器中来消除许多在线性时间上不相似的单词。如果两个字符串都是字谜，则无论排序如何，两个字符串中所有字符的总异或必须为零。这是因为任何与自身异或的东西都变为零。
当然，反之亦然。仅仅因为累加器为零并不意味着我们有一个字谜匹配。
使用这些信息，我们可以在没有排序的情况下消除许多非字谜，至少短路非字谜的情况。
#include <iostream>
#include <string>
#include <algorithm>
//
// return a sorted copy of a string
//
std::string sorted(std::string in)
{
std::sort(in.begin(), in.end());
return in;
}
//
// check whether xor-ing the values in two ranges results in zero.
// @pre first2 addresses a range that is at least as big as (last1-first1)
//
bool xor_is_zero(std::string::const_iterator first1,
std::string::const_iterator last1,
std::string::const_iterator first2)
{
char x = 0;
while (first1 != last1) {
x ^= *first1++;
x ^= *first2++;
}
return x == 0;
}
//
// deduce whether two strings are the same length
//
bool same_size(const std::string& l, const std::string& r)
{
return l.size() == r.size();
}
//
// deduce whether two words are anagrams of each other
// I have passed by const ref because we may not need a copy
//
bool is_anagram(const std::string& l, const std::string& r)
{
return same_size(l, r)
&& xor_is_zero(l.begin(), l.end(), r.begin())
&& sorted(l) == sorted(r);
}
// test
int main() {
using namespace std;
auto s1 = "apple"s;
auto s2 = "eppla"s;
cout << is_anagram(s1, s2) << '\n';
s2 = "pppla"s;
cout << is_anagram(s1, s2) << '\n';
return 0;
}
预期的：
1
0