while循环中使用.replace()的时间复杂度分析及括号匹配算法疑问

问题背景 #

给定一个括号字符串，统计其中未配对的括号数量。匹配正确的定义是：每个左括号都能与后续的右括号配对，每个右括号都能与之前的左括号配对。示例如下：

• 输入"(()"，输出1
• 输入"(())"，输出0
• 输入"())("，输出2

解法与疑问 #

我最初实现了基于栈的解法，时间复杂度O(N)，空间复杂度O(N)。同事提示可以用常数空间解法，于是我写出了下面的代码：

def bracket_match(s):
    while s and '()' in s:
        s = s.replace('()', '')
    return len(s)

我认为这个解法空间复杂度是O(1)，但同事指出它的时间复杂度是O(N²)，理由是replace()方法是线性时间，加上while循环的线性次数，两者叠加会导致平方级复杂度。这个说法是否合理？

复杂度分析 #

同事的说法是合理的，原因如下：

• 每次replace('()', '')操作需要遍历当前字符串，时间复杂度为O(k)（k是当前字符串长度）
• while循环的次数取决于字符串中括号的嵌套层级。最坏情况比如嵌套的括号串"((((...))))"（N个字符，N为偶数），每次循环只能去掉最内层的一对括号，字符串长度减少2，循环次数为O(N)次。每次循环的操作时间分别为O(N)、O(N-2)、O(N-4)...，总和为O(N²)
• 只有当字符串中都是连续的"()"对时，循环仅执行1次，时间复杂度为O(N)，这是最好情况，但整体最坏时间复杂度仍是O(N²)

最优常数空间解法 #

如果要实现O(N)时间+O(1)空间的最优解法，可以用两个计数器分别记录未匹配的左、右括号数量：

def bracket_match(s):
    left = 0  # 未匹配的左括号数
    right = 0  # 未匹配的右括号数
    for char in s:
        if char == '(':
            left += 1
        else:
            if left > 0:
                left -= 1
            else:
                right += 1
    return left + right

遍历一次字符串即可完成统计，完全符合常数空间要求，同时时间复杂度稳定为O(N)。

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