Java字符串不可变性为何会导致搜索推荐系统问题产生额外O(m²)时间复杂度？

兄弟，这个问题我当初刚啃Java字符串特性的时候也卡过，咱们掰开揉碎了说就清楚了！

首先得明确Java里String的核心特性：一旦创建就完全不可修改。你平时写的prefix + 'a'这种拼接操作，根本不是在原来的prefix字符串后面加字符，而是会新建一个全新的String对象——把原来prefix里的所有字符，加上新的'a'，一起复制到新对象的字符数组里，最后返回这个新的String。

现在结合LeetCode那个搜索推荐的场景：我们要处理长度为m的搜索词，每一步都要生成当前的前缀（比如搜"cat"，就要依次生成"c"、"ca"、"cat"），然后用这个前缀去Trie里找推荐词。

如果用String来维护这个前缀，每一步的开销是这样的：

• 生成第一个前缀"c"：复制1个字符，耗时O(1)
• 生成第二个前缀"ca"：要把原来的"c"（1个字符）和新的"a"一起复制到新字符串，耗时O(2)
• 生成第三个前缀"cat"：复制"ca"（2个字符）和"t"，耗时O(3)
• ...
• 生成第m个前缀（完整搜索词）：复制m个字符，耗时O(m)

把这些时间加起来：1+2+3+...+m = m*(m+1)/2，这妥妥就是**O(m²)**的时间复杂度！这就是所谓的额外开销——因为如果用可变的字符容器（比如StringBuilder），情况就完全不同：

StringBuilder的append操作是直接在内部的字符数组里追加（只要数组容量够，就不用扩容复制），每一步append都是O(1)的分摊时间。如果是在递归遍历Trie的场景里，我们还可以先append字符，递归结束后再delete最后一个字符，全程不需要复制整个前缀字符串，总时间就是O(m)，完全没有那个平方级的开销。

举个直观的代码对比：

踩坑写法（产生O(m²)开销）：

// 遍历搜索词的每个字符，用String拼接前缀
String currentPrefix = "";
for (char c : searchWord.toCharArray()) {
    currentPrefix += c; // 每次都新建String，复制全部已有字符
    // 用currentPrefix去Trie查询推荐词
}

优化写法（避免额外O(m²)）：

// 用StringBuilder维护可变前缀
StringBuilder prefixBuilder = new StringBuilder();
for (char c : searchWord.toCharArray()) {
    prefixBuilder.append(c); // 直接追加，无全量复制
    String currentPrefix = prefixBuilder.toString();
    // 用currentPrefix去Trie查询推荐词
}

（注：如果是递归场景，我们可以不用每次toString，而是直接用StringBuilder传递，递归后回退，连这部分复制都能省）

说白了，就是String的不可变性逼得我们每次扩展前缀都要做一次全量复制，多次操作下来，复制的总字符数就变成了平方级，这就是那个额外O(m²)时间复杂度的来源。

备注：内容来源于stack exchange，提问作者Cam