关于字符串操作及Leetcode有效括号移除解法的时间与空间复杂度问询

Hey there! Let's tackle your two complexity questions one by one.

问题一：仅做常数字符操作+字符串反转，空间复杂度是否为线性？ #

答案是肯定的，空间复杂度为O(n)，不是常数。

这里的关键是Python字符串的核心特性：它是不可变类型。你以为的“反转操作”（比如用s[::-1]）并不是原地修改原字符串，而是会创建一个全新的、与原字符串长度相同的副本——这个副本需要占用O(n)的内存空间。哪怕你对每个字符的操作都是常数时间，只要涉及到字符串的反转（或任何修改，比如替换、切片），都会生成新的线性空间字符串，所以整体空间复杂度是线性的。

问题二：你的有效括号解法的时间&空间复杂度分析 #

先直接说结论：你的时间复杂度判断不对（最坏是O(n²)），空间复杂度也不是O(1)，而是O(n)。让我拆解原因：

时间复杂度：最坏情况为O(n²) #

你的代码里有个隐形的性能瓶颈：

• 在while循环中，你用s.replace(s[pointer], " ", 1)删除多余的)。str.replace()每次执行都要遍历整个字符串（O(n)时间）来找到第一个匹配的字符，然后生成新字符串。如果字符串里有O(n)个需要删除的)（比如全是)的极端情况），这部分的总时间就会变成O(n×n)=O(n²)。
• 后面的两次反转、替换(、删除空格这些操作都是O(n)，但前面的replace操作在最坏情况会主导时间复杂度，所以整体不是O(n)。

空间复杂度：O(n) #

你提到“直接对输入进行操作”，但Python字符串不可变的特性决定了：所有看似修改字符串的操作，本质都是创建新的字符串副本：

• 每次replace都会生成一个长度接近O(n)的新字符串；
• 两次s[::-1]反转操作也会各自生成O(n)大小的新字符串；
• 哪怕你用变量s覆盖旧值，每次生成的新字符串都需要占用O(n)的内存空间。
  所以整体空间复杂度是线性的O(n)，而非常数空间。

小优化建议（供参考） #

如果想把时间复杂度优化到O(n)（这是这类问题的最优水平），可以改用栈来记录需要保留的括号位置，或者分两次遍历：第一次删除多余的)，第二次反转字符串删除多余的(，全程用列表来构建结果（列表是可变类型，修改操作是O(1)时间），避免使用str.replace这种每次都遍历整个字符串的操作。

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