如何以优于O(n²)的复杂度生成字符串的所有单字符缺失子串？

首先明确：生成所有单字符缺失子串的算法，理论上无法做到低于O(n²)的时间复杂度。因为对于长度为n的输入字符串，最终会生成n个长度为n-1的子串，总字符数为n*(n-1)，这本身就是O(n²)的量级——任何需要实际构造并输出这些子串的算法，都必须处理这么多字符，因此时间复杂度的下限就是O(n²)。

你的现有实现确实是O(n²)的时间复杂度，但可以通过减少内存拷贝的常数开销来提升实际运行效率：

原代码的问题点 #

原代码中每次通过inputString.substr(0, i) + inputString.substr(i + 1)拼接子串，会产生两个临时字符串（substr的结果），再进行一次字符串拼接，这会带来额外的内存分配和拷贝操作，增加了常数时间成本。

优化后的实现 #

下面的实现通过预分配内存、直接复制字符的方式，减少临时对象的创建和内存拷贝：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

std::vector<std::string> generateSubstrings(const std::string& inputString) {
    const size_t n = inputString.length();
    std::vector<std::string> substrings;
    substrings.reserve(n); // 预分配vector的空间，避免动态扩容开销

    for (size_t i = 0; i < n; ++i) {
        std::string sub;
        sub.reserve(n - 1); // 预分配单个子串的空间
        // 复制前i个字符
        std::copy(inputString.begin(), inputString.begin() + i, std::back_inserter(sub));
        // 复制i+1到末尾的字符
        std::copy(inputString.begin() + i + 1, inputString.end(), std::back_inserter(sub));
        substrings.push_back(sub);
    }
    return substrings;
}

int main() {
    std::string inputString = "A13";
    std::vector<std::string> result = generateSubstrings(inputString);
    
    for (const std::string& substring : result) {
        std::cout << substring << std::endl;
    }

    return 0;
}

优化说明 #

1. 预分配内存：
   • 给substrings调用reserve(n)，提前分配足够容纳n个子串的空间，避免vector多次扩容时的内存重新分配和拷贝。
   • 给每个子串sub调用reserve(n-1)，提前分配刚好容纳n-1个字符的空间，避免字符串拼接过程中的动态扩容。
2. 直接字符复制：使用std::copy直接将原字符串的字符复制到目标子串中，避免了substr产生的临时字符串，减少了内存拷贝的次数。

这些优化不会改变算法的时间复杂度（仍然是O(n²)），但能显著降低实际运行时的常数开销，让代码在处理较长字符串时更快。

内容的提问来源于stack exchange，提问作者La Bola Al Riel