如何提高混淆代码的性能？

Question

我需要完成函数scramble(str1, str2)，如果str1的一部分字符可以重新排列以匹配str2，则返回true，否则返回false。我该如何改进这段代码的性能？ 例如，如果str1和str2中有超过200k个字符，性能非常差。

bool scramble(const string& s1, const string& s2) 
{
    string reference = s2;
    string inputStr = s1;
    size_t refLen = reference.length();
    size_t lenCounter = 0;

    for (auto n = 0; n < reference.length(); n++)
    {
        auto tempLetter = reference[n];
        size_t letterPos = inputStr.find(tempLetter);
        if (letterPos != string::npos)
        {
            lenCounter++;
            inputStr.erase(letterPos, 1);
            if (lenCounter == refLen)
            {
                return true;
            }
        }
        else
            return false;
    }
    if (refLen == lenCounter)
        return true;
    else
        return false;
}

这是一个符合我的要求的现成解决方案。这个解决方案的想法是由@Dave提供的。

bool scramble(const string& s1, const string& s2)
{
    string ref = s2;
    string input = s1;
    string result = "";
    char tempLetter = '\0';
 
    sort(ref.begin(), ref.end());
    sort(input.begin(), input.end());
   
    map<char, int> letters;

    for (auto n = 0; n < input.length(); n++)
    {
        tempLetter = input[n];
        map<char, int> ::iterator it = letters.find(tempLetter);
        if (it == letters.end())
        {
            letters.insert(make_pair(tempLetter, 0));
            letters.at(tempLetter) = 1;
        }
        else
        {
            letters.at(tempLetter) += 1;
        }
    }
    for (auto i = 0; i < ref.length(); i++)
    {
        tempLetter = ref[i];
        map<char, int> ::iterator it = letters.find(tempLetter);
        if (it != letters.end() && letters.at(tempLetter) >=0)
        {
            letters.at(tempLetter) -= 1;
            if (letters.at(tempLetter) < 0)
                return false;
            result.push_back(tempLetter);
        }
    }
    if (result!=ref)
        return false;
    else
        return true;
}

- Roofin88

---

https://codereview.stackexchange.com/ - undefined

你知道如何快速检查变位词吗？如果不知道，可以查一下，这是一个相当有名的简单问题，每个人和他们的狗都有自己的版本。 - undefined

@n.m.couldbeanAI 通常你是正确的。然而，对于不具备可扩展性的程序，我们有一个例外情况。如果代码在小规模输入上能够正确运行（输出正确的值），那么该代码将符合我们的规模规则。此外，如果你仍然不相信我，我想指出我们的 "time-limit-exceeded" 标签给你参考。感谢你帮助我们将离题的问题远离代码审查。 - undefined

欢迎来到Scicomp！你可以尝试的一种方法是对这两个字符串进行排序，然后开始查找。这样一来，你可以大大减少查找负结果所需的时间，只是要付出对这两个字符串进行排序的代价。可以尝试这样做：std::sort(std::begin(array), std::end(array)) - undefined

另一个想法是进行一次遍历，计算出现的"a"、"b"等字符的数量，并保持一个表格。然后对第二个数组进行相同操作。接着检查数组中是否有足够的"a"和"b"。这样可以将复杂度降低为线性，但需要一些额外的内存来进行计数。 - undefined

Answer 1

如果字符串的长度不相同，则返回false。

使用计数哈希。

对于第一个单词，在映射中递增每个字母的计数。对于第二个单词，递减每个字母的计数。

在递减过程中，如果一个字母的计数将会减到零以下，则返回false。如果成功遍历到最后，则返回true。

对于n个字母，时间复杂度为O(n)。

除了使用计数哈希，你还可以使用一个整数数组，数组的索引对应相关字母表中的每个字符，并将其用于计数。

- Dave

---

非常感谢，你的回答真的帮了我很多。我根据我的情况进行了优化，现在它完美地运行了。还要感谢你没有提供现成的解决方案，这对我的C++学习非常有帮助。 - undefined

最后，如果总数没有回到零，就返回false。或者在a.size() != b.size()的情况下提前退出，这种情况下你根本不需要进行任何哈希操作。 - undefined

@BenVoigt 说得好。已编辑。谢谢。 - undefined

你真的需要一张地图吗？我会为每个字母使用一个计数器数组。 - undefined

@VladFeinstein 我在最后一句话中的意思就是：不要使用计数哈希，而是使用一个整数数组，每个字符对应一个索引。这样清楚吗？ - undefined

Answer 2

我会以两个原因稍微改写它：

1. 可读性和可维护性 2. 复杂性

假设 m = sizeof s1; 和 n = sizeof s2;，并且 n 应该比 m 大。

首先对字符串进行排序将花费 O(nlog(n)) 的时间，但是然后在一次遍历中，您就可以得到输出结果，这意味着我的混淆函数的复杂度为：

O(n+nlogn) = O(nlongn)

然而，在你的情况下，复杂度是 O(n*m)。

这是我会写的方式：

bool is_scramble(std::string s1, std::string s2) 
{
    if (s2.size() < s1.size()) return false;

    std::ranges::sort(s1);
    std::ranges::sort(s2);

    return std::ranges::includes(s2, s1);
}

如评论中所提到的，您可以使用计数排序（在ASCII或EBCDIC的限制下）来降低时间复杂度，然后改用以下代码。

这确实需要额外的256字节存储空间（在ASCII或EBCDIC的限制下）。我个人认为，这种方法可读性较差。

bool is_scramble2(std::string s1, std::string s2) 
{
    // s1 needs to be contain in s2
    if (s2.size() < s1.size()) return false;

    constexpr int maxChar = 256; // Assuming ASCII character set
    std::array<int, maxChar> count = {0};

    // Count the occurrences of each character in the string
    for (char c : s2) {
        count[static_cast<int>(c)]++;
    }

    for(const auto c : s1) {
        if (count[static_cast<int>(c)] <= 0) return false;
        count[static_cast<int>(c)]--;
    }
    return true;
}

- Avi Lachmish

---

使用计数排序甚至可以达到O(256 * n)的时间复杂度（而且排序部分甚至是不必要的，因为只有计数部分就足够检查包含性）。 - undefined

是的，你说得对，但是你假设了ASCII字符并使用了额外的256个字节。 - undefined

我不假设ASCII（也支持EBCDIC）。 - undefined

抱歉，你又是对的...我会更新我的回答 - undefined