我来给你讲解 LeetCode 第 301 题「删除无效的括号」。

题目描述

给你一个由括号和小写字母组成的字符串 s，你需要删除最少数量的无效括号，使得字符串变得有效。返回所有可能的结果（顺序任意）。

有效字符串需满足：

1. 左括号 '(' 和右括号 ')' 数量相等；
2. 且每个左括号对应的右括号必须在其后面（即括号匹配正确）。

示例：

输入: "()())()"
输出: ["()()()", "(())()"]

解题思路

第一步：理解问题本质

这个问题需要找到所有通过删除最少括号得到有效字符串的结果。关键点：

• 我们需要删除最少数量的括号
• 可能存在多个合法结果
• 字符串中可能包含字母，这些字母不能删除

第二步：分析需要删除多少括号

我们可以先遍历一次字符串，统计需要删除多少左括号和右括号：

• 遇到 '('：左括号计数加1
• 遇到 ')'：如果左括号计数大于0，说明有匹配的左括号，左括号计数减1；否则说明这个右括号多余，需要删除

遍历结束后，左括号计数就是还需要删除的左括号数量。

第三步：回溯算法设计

使用回溯算法来尝试所有可能的删除方案：

def removeInvalidParentheses(s):
    # 统计需要删除的左括号和右括号数量
    left_remove, right_remove = 0, 0
    for char in s:
        if char == '(':
            left_remove += 1
        elif char == ')':
            if left_remove > 0:
                left_remove -= 1
            else:
                right_remove += 1
    
    result = set()
    
    def backtrack(index, left_count, right_count, left_rem, right_rem, path):
        # index: 当前处理到的位置
        # left_count: 当前路径中左括号数量
        # right_count: 当前路径中右括号数量
        # left_rem: 剩余可删除的左括号数量
        # right_rem: 剩余可删除的右括号数量
        # path: 当前构建的字符串
        
        if index == len(s):
            # 处理完整个字符串
            if left_rem == 0 and right_rem == 0 and left_count == right_count:
                result.add(path)
            return
        
        char = s[index]
        
        # 如果当前字符是括号，可以选择删除
        if char == '(' and left_rem > 0:
            backtrack(index + 1, left_count, right_count, left_rem - 1, right_rem, path)
        elif char == ')' and right_rem > 0:
            backtrack(index + 1, left_count, right_count, left_rem, right_rem - 1, path)
        
        # 选择不删除当前字符
        if char == '(':
            backtrack(index + 1, left_count + 1, right_count, left_rem, right_rem, path + char)
        elif char == ')':
            if left_count > right_count:  # 只有左括号比右括号多时才能添加右括号
                backtrack(index + 1, left_count, right_count + 1, left_rem, right_rem, path + char)
        else:  # 字母字符，必须保留
            backtrack(index + 1, left_count, right_count, left_rem, right_rem, path + char)
    
    backtrack(0, 0, 0, left_remove, right_remove, "")
    return list(result)

第四步：优化剪枝策略

为了进一步提高效率，我们可以添加更多剪枝条件：

1. 提前终止：如果剩余字符数不足以构建有效字符串，提前返回
2. 括号有效性检查：在过程中确保右括号不会超过左括号
3. 去重处理：使用集合避免重复结果

第五步：完整优化代码

def removeInvalidParentheses(s):
    # 统计需要删除的括号数量
    left_remove, right_remove = 0, 0
    for char in s:
        if char == '(':
            left_remove += 1
        elif char == ')':
            if left_remove > 0:
                left_remove -= 1
            else:
                right_remove += 1
    
    result = set()
    
    def backtrack(index, left_count, right_count, left_rem, right_rem, path):
        if index == len(s):
            if left_rem == 0 and right_rem == 0 and left_count == right_count:
                result.add(path)
            return
        
        char = s[index]
        
        # 剪枝：如果剩余可删除数量超过剩余字符数，不可能成功
        if left_rem + right_rem > len(s) - index:
            return
        
        # 选择删除当前字符（如果是括号）
        if char == '(' and left_rem > 0:
            backtrack(index + 1, left_count, right_count, left_rem - 1, right_rem, path)
        elif char == ')' and right_rem > 0:
            backtrack(index + 1, left_count, right_count, left_rem, right_rem - 1, path)
        
        # 选择保留当前字符
        if char == '(':
            backtrack(index + 1, left_count + 1, right_count, left_rem, right_rem, path + char)
        elif char == ')':
            if left_count > right_count:  # 确保括号有效性
                backtrack(index + 1, left_count, right_count + 1, left_rem, right_rem, path + char)
        else:
            backtrack(index + 1, left_count, right_count, left_rem, right_rem, path + char)
    
    backtrack(0, 0, 0, left_remove, right_remove, "")
    return list(result)

第六步：算法分析

• 时间复杂度：最坏情况 O(2^n)，n 为字符串长度，但剪枝大大减少了实际搜索空间
• 空间复杂度：O(n²)，主要取决于递归栈深度和结果存储

第七步：测试验证

用示例测试：

print(removeInvalidParentheses("()())()"))  # 输出: ["()()()", "(())()"]
print(removeInvalidParentheses("(a)())()")) # 输出: ["(a)()()", "(a())()"]

这个算法通过精确计算需要删除的括号数量，配合回溯和剪枝，高效地找到了所有可能的最优解。