为什么java中字符串的不变性会导致这个问题额外的运行时间：https://leetcode.com/problems/search-suggestions-system/solution/

Question

对于这个问题：https://leetcode.com/problems/search-suggestions-system/solution/，解决方案 1 指出，对于 Java，_“由于字符串，存在 O(m^2) 的额外复杂性由于是不可变的，这里 m 是 searchWord 的长度。”）我对此真的很摸不着头脑。为什么字符串的不变性会导致 O(m^2) 的额外运行时间？

Answer 1

正如评论中提到的，请阅读如何提问，如果您的问题不包含代码，而我们无需滚动外部资源，它可能会被关闭。该链接可以，只需包含代码片段或您使用过的来源即可。
为了回答你的问题，每次连接字符串时，都会在 O(N) 时间内完成，因为每次连接都必须创建一个新字符串，source。
所以在解决方案中：

for (char c : searchWord.toCharArray()) {
    prefix += c;
    ...
}

由于每次连接 N 次的时间复杂度为 O(N)，因此增加了 O(N^2) 时间复杂度，这与 C++ 等语言相反，其中字符串连接时间复杂度基于数组增长（如果每次都会发生增长，但在大多数情况下都是恒定的时间）。