使用 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，函数 returns 为真。

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

Answer 1

可以单独统计字数：

bool isPermutation(std::string a, std::string b)
{
    if(a.length() != b.length())
        return false;

    assert(a.length() <= INT_MAX);
    assert(b.length() <= INT_MAX);

    int counts[256] = {};
    for (unsigned char ch : a)
        ++counts[ch];
    for (unsigned char ch : b)
        --counts[ch];
    for (int count : counts)
        if (count)
            return false;

    return true;
}

Answer 2

不需要 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 的答案，它的复杂性是线性的。

Link is_permutation 的文档：http://en.cppreference.com/w/cpp/algorithm/is_permutation

Link sort 的文档： http://en.cppreference.com/w/cpp/algorithm/sort

如果需要 UTF-8 支持，一种（稍微）更复杂的方法

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

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

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);

缺点是现在 John Zwinck 的方法变得不太实用了。您必须为 1114112 个元素声明数组，因为这是实际存在的可能的 Unicode 字符数。

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

Answer 3

std::sort( strOne.begin(), strOne.end() );
std::sort( strTwo.begin(), strTwo.end() );    
return strOne == strTwo;

足够了。

我的建议是使用std::unordered_map

即

std::unordered_map< char, unsigned > umapOne;
std::unordered_map< char, unsigned > umapTwo;
for( char c : strOne ) ++umapOne[c];
for( char c : strTwo ) ++umapTwo[c];
return umapOne == umapTwo;

作为优化，您可以在顶部添加解决方案

if( strOne.size() != strTwo.size() ) return false;

更好的std::unordered_map解决方案，

if( strOne.size() != strTwo.size() ) return false; // required
std::unordered_map< char, int > umap;
for( char c : strOne ) ++umap[c];
for( char c : strTwo ) if( --umap[c] < 0 )  return false;
return true;

如果你只是想解决一个问题而不知道如何去做，你可以使用std::is_permutation

return std::is_permutation( strOne.begin(), strOne.end(), strTwo.begin(), strTwo.end() );

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

Determine if A is permutation of B using ASCII values

c++

permutation

c++11

不需要 UTF-8 支持的简单方法

如果需要 UTF-8 支持，一种（稍微）更复杂的方法