如何解决LeetCode有效括号变种问题：统计最少需移除括号数

问题回顾 #

原题是判断字符串是否为有效括号，变种题要计算让字符串变有效所需移除的最少括号数，有效字符串需满足：

1. 开括号必须用同类型闭括号闭合；
2. 开括号得按正确顺序闭合；
3. 每个闭括号都有对应同类型开括号。

已知测试用例的预期结果：

• ( [ ) ] → 返回2
• ( [ { } ] ) → 返回0
• ( [ ] ] ) → 返回1
• ( [ { ] ) → 返回1

核心矛盾点 #

你之前的两种解法各有缺陷：

• 常规栈解法处理( [ { ] )时返回5，因为它只会统计所有单独不匹配的括号，没考虑移除一个括号就能让剩余括号全部匹配；
• 另一种解法能得到( [ { ] )的正确结果1，但会把( [ ) ]误判为0，明显忽略了括号类型和顺序的匹配要求。

正确思路：最长有效括号子序列法 #

最少移除数量 = 字符串总长度 - 最长有效括号子序列的长度。

这个思路的核心是：找到字符串里最长的一段符合要求的有效括号序列，剩下的就是必须移除的括号，这样移除的数量自然最少。

如何计算最长有效括号子序列 #

用动态规划即可实现，步骤如下：

1. 定义dp[i]为以第i个字符结尾的最长有效括号子序列长度，初始化全为0；
2. 准备括号映射表：{')':'(', ']':'[', '}':'{'}，方便快速匹配闭括号对应的开括号；
3. 从字符串第二个字符开始遍历：
   • 如果当前字符是闭括号：
     • 第一种情况：前一个字符正好是对应的开括号，dp[i]等于前前位置的dp值加2（若存在前前位置，否则直接为2）；
     • 第二种情况：前一个字符是闭括号，先找到前一个有效子序列起始位置的前一个字符，若该字符是当前闭括号对应的开括号，dp[i]等于前一个有效子序列的长度，加上该开括号前面的有效子序列长度，再加上2；
4. 遍历过程中记录最大的dp值，即最长有效括号子序列的长度；
5. 最后用字符串总长度减去这个最大长度，就是最少需要移除的括号数。

代码示例 #

def min_remove_to_make_valid(s):
    n = len(s)
    if n == 0:
        return 0
    dp = [0] * n
    bracket_map = {')': '(', ']': '[', '}': '{'}
    max_valid_len = 0
    for i in range(1, n):
        if s[i] in bracket_map:
            match_open = bracket_map[s[i]]
            # 前一个字符是对应开括号
            if s[i-1] == match_open:
                dp[i] = dp[i-2] + 2 if i >= 2 else 2
            else:
                # 寻找前面可能匹配的开括号位置
                prev_open_pos = i - dp[i-1] - 1
                if prev_open_pos >= 0 and s[prev_open_pos] == match_open:
                    # 加上开括号前面的有效长度
                    dp[i] = dp[i-1] + (dp[prev_open_pos-1] if prev_open_pos >=1 else 0) + 2
            max_valid_len = max(max_valid_len, dp[i])
    return n - max_valid_len

测试验证：

• ( [ ) ]：总长度4，最长有效子序列长度2，4-2=2，正确；
• ( [ { } ] )：总长度6，最长有效子序列长度6，6-6=0，正确；
• ( [ ] ] )：总长度5，最长有效子序列长度4，5-4=1，正确；
• ( [ { ] )：总长度5，最长有效子序列长度4，5-4=1，正确。

错误解法的问题根源 #

1. 常规栈解法仅统计单个不匹配的括号，没考虑移除一个括号就能让后续多个括号匹配的连锁效应；
2. 另一种错误解法跳过了括号类型和顺序的校验，将原本不合法的序列误判为有效，导致结果错误。

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