c++ - 使用 ASCII 值确定 A 是否是 B 的排列

Question

我编写了一个函数来确定字符串 a 是否是字符串 b 的排列。定义如下:

bool isPermutation(std::string a, std::string b){
    if(a.length() != b.length())
        return false;
    int a_sum, b_sum;
    a_sum = b_sum = 0;
    for(int i = 0; i < a.length(); ++i){
        a_sum += a.at(i);
        b_sum += b.at(i);
    }
    return a_sum == b_sum;
}

我的方法的问题是，如果 a = 600000 且 b = 111111，该函数将返回 true。

有什么方法可以保持我解决这个问题的一般方法(而不是对字符串进行排序然后执行strcmp)并保持正确性？

Answer 1

如果您不需要 UTF-8 支持，这是一个简单的方法

解决这个问题出奇的简单。标准库中有一个函数可以处理这个问题。

假设a和b是两个string:

return is_permutation(a.begin(), a.end(), b.begin(), b.end());

或者，如果您还无法访问 C++14:

return a.size() == b.size() && is_permutation(a.begin(), a.end(), b.begin());

请注意，尽管这种复杂性只能保证不低于字符串大小的二次方。因此，如果这很重要，那么对两个字符串进行排序确实是一个更好的解决方案:

string aa(a); sort(aa.begin(), aa.end());
string bb(b); sort(bb.begin(), bb.end());
return (aa == bb);

如果这也太慢，请使用上面 John Zwinck 的答案，它的复杂性是线性的。

链接到 is_permutation 的文档:http://en.cppreference.com/w/cpp/algorithm/is_permutation

链接到排序的文档: http://en.cppreference.com/w/cpp/algorithm/sort

如果需要 UTF-8 支持，则采用(稍微)更复杂的方法

上述方法在 UTF-8 字符串上可能会失败。这里的问题是UTF-8是一种多字节字符编码，也就是说，单个字符可以编码在多个char变量中。上面提到的方法都没有意识到这一点，并且都假设单个字符也是一个 char 变量。这些方法失败的两个 UTF-8 字符串的示例如下: http://ideone.com/erfNmC

解决方案可能是暂时将我们的UTF-8字符串复制为固定长度的UTF-32编码字符串。假设a和b是两个UTF-8编码的string:

u32string a32 = wstring_convert<codecvt_utf8<char32_t>, char32_t>{}.from_bytes(a);
u32string b32 = wstring_convert<codecvt_utf8<char32_t>, char32_t>{}.from_bytes(b);

然后你就可以在这些UTF-32编码的字符串上正确使用上述函数了:

return is_permutation(a32.begin(), a32.end(), b32.begin(), b32.end()) << '\n';

或者:

sort(a32.begin(), a32.end());
sort(b32.begin(), b32.end());
return (aa == bb);

缺点是现在约翰·兹温克的方法变得不太实用。您必须声明包含 1114112 个元素的数组，因为这是实际存在的可能的 Unicode 字符数。

有关转换为 UTF-32 的更多信息:http://en.cppreference.com/w/cpp/locale/wstring_convert/from_bytes