如何提升C++中scramble字符串匹配函数的性能？

首先分析现有代码的性能瓶颈：

• 第一段代码：每次调用find和erase都是O(n)级别的操作，嵌套循环后时间复杂度达到O(m*n)，当字符串长度达到20万时，运算量会飙升到数十亿级别，完全无法高效运行。
• 第二段代码：虽然做了排序，但额外使用了map（红黑树实现），插入和查找操作都是O(logk)（k为字符种类数），同时还维护了冗余的result字符串做最终比较，整体时间复杂度为O(n logn + m logk)，对于大字符串依然不够高效。

最优优化方案：基于字符计数数组的线性时间实现 #

利用字符的ASCII范围有限的特性，用数组代替哈希表/树结构，实现O(n + m)的线性时间复杂度，内存占用也极低。

优化后的代码：

#include <string>
#include <cstring>

bool scramble(const std::string& s1, const std::string& s2) {
    // 针对ASCII字符初始化计数数组，若仅处理小写字母可缩小为26长度
    int charCount[256] = {0};
    memset(charCount, 0, sizeof(charCount));

    // 统计s1中每个字符的出现次数
    for (char c : s1) {
        charCount[static_cast<unsigned char>(c)]++;
    }

    // 遍历s2，逐个扣除计数
    for (char c : s2) {
        unsigned char uc = static_cast<unsigned char>(c);
        if (charCount[uc] == 0) {
            return false;
        }
        charCount[uc]--;
    }

    return true;
}

优化点说明 #

1. 用数组替代map：数组的访问和更新都是O(1)操作，比map的O(logk)快得多，且无需额外的树结构开销。
2. 线性时间复杂度：仅需两次遍历（一次统计s1，一次校验s2），总时间复杂度为O(len(s1) + len(s2))，处理20万长度的字符串只需要约40万次操作，性能提升几个数量级。
3. 避免冗余操作：不需要排序、字符串修改或结果拼接，直接通过计数校验即可完成判断，减少了内存拷贝和额外计算。
4. 内存高效：固定大小的256整数数组（仅1KB左右），远小于原代码中复制字符串或维护map的内存开销。

额外优化（若仅处理小写字母） #

如果确定输入仅包含小写英文字母，可以将数组缩小为26个元素，进一步减少内存占用：

bool scramble(const std::string& s1, const std::string& s2) {
    int charCount[26] = {0};

    for (char c : s1) {
        charCount[c - 'a']++;
    }

    for (char c : s2) {
        int idx = c - 'a';
        if (charCount[idx] == 0) {
            return false;
        }
        charCount[idx]--;
    }

    return true;
}

内容的提问来源于stack exchange，提问作者Roofin88