301. 删除无效的括号
题目描述
给你一个由若干括号和字母组成的字符串 s，删除最少数量的无效括号，使得输入的字符串有效，并返回所有可能的结果。
答案可以按 任意顺序 返回。
示例
示例 1：
输入：s = "()())()"
输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
解题思路
第一步：理解问题本质
我们需要删除最少数量的括号使字符串合法。关键问题是：如何判断需要删除多少个括号？
第二步：统计需要删除的括号数
遍历字符串，维护两个计数器：
lremove：需要删除的左括号数rremove：需要删除的右括号数
规则：
- 遇到
'('，lremove++ - 遇到
')'：如果lremove > 0，说明有匹配的'('，lremove--；否则rremove++
例如 "()())()"，从左到右扫一遍：
- 遇到
'('：暂时多出一个左括号，lremove += 1 - 遇到
')'：若lremove > 0，说明它能和之前多出的左括号配对，lremove -= 1；否则这个右括号没人配，rremove += 1
| 下标 | 字符 | lremove | rremove | 说明 |
|---|---|---|---|---|
| 0 | ( | 1 | 0 | 多出一个左括号 |
| 1 | ) | 0 | 0 | 与下标 0 的左括号配对 |
| 2 | ( | 1 | 0 | 多出一个左括号 |
| 3 | ) | 0 | 0 | 与下标 2 的左括号配对 |
| 4 | ) | 0 | 1 | 没有左括号可配，右括号多余 |
| 5 | ( | 1 | 1 | 多出一个左括号 |
| 6 | ) | 0 | 1 | 与下标 5 的左括号配对 |
结果：lremove = 0、rremove = 1，即只需删掉 1 个右括号。
扫完之后剩下的 lremove 就是多余的左括号数，两者合起来就是最少要删的括号数。
第三步：回溯法
思路：尝试删除多余的括号，用 isValid 验证结果。
剪枝策略：
- 跳过连续相同的括号（避免重复结果）
- 如果剩余字符不足以删除所需数量，提前返回
第四步：BFS 解法
核心洞察：
- 逐层删除括号，第一次遇到合法字符串时即为最少删除
- 每层删除一个括号，生成所有可能的新字符串
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
def isValid(s):
# 合法判定：任意前缀中右括号不能多于左括号，最终数量必须相等
count = 0
for c in s:
if c == '(':
count += 1
elif c == ')':
count -= 1
# 前缀已经失衡，后面再多左括号也救不回来
if count < 0:
return False
return count == 0
# ans 收集本层的所有合法串，同层意味着删掉的括号数相同
ans = []
currSet = set([s])
# 逐层扩展：第 k 层是删掉 k 个括号后的所有可能串
while True:
# 本层可能不止一个合法答案，全部都要留下
for ss in currSet:
if isValid(ss):
ans.append(ss)
# 第一次出现合法串，删除数就是最少的，直接返回整层
if len(ans) > 0:
return ans
nextSet = set()
for ss in currSet:
# 只删括号，字母一个都不能动
for i in range(len(ss)):
if ss[i] == '(' or ss[i] == ')':
# 用集合去重：不同的删法可能得到同一个串
nextSet.add(ss[:i] + ss[i+1:])
# 本层没有答案，带着删除数加一的所有结果进入下一层
currSet = nextSet
完整代码实现
算法可视化 · 逐帧回放这道题的代码4 帧 · 录制输入 "(a)())()"
from typing import List
class Solution:
"""
删除无效的括号 - 回溯法
先统计需要删除的左右括号数量，然后用回溯尝试所有删除方案
时间复杂度：O(2^n) 最坏情况
空间复杂度：O(n) 递归栈
"""
def removeInvalidParentheses(self, s: str) -> List[str]:
res = []
lremove, rremove = 0, 0
# 统计需要删除的括号数
for c in s:
if c == '(':
lremove += 1
elif c == ')':
if lremove == 0:
rremove += 1
else:
lremove -= 1
def isValid(str):
cnt = 0
for c in str:
if c == '(':
cnt += 1
elif c == ')':
cnt -= 1
if cnt < 0:
return False
return cnt == 0
def helper(s, start, lremove, rremove):
if lremove == 0 and rremove == 0:
if isValid(s):
res.append(s)
return
for i in range(start, len(s)):
# 跳过连续相同的括号，避免重复结果
if i > start and s[i] == s[i - 1]:
continue
# 剩余字符不足以删除所需数量
if lremove + rremove > len(s) - i:
break
# 尝试去掉一个左括号
if lremove > 0 and s[i] == '(':
helper(s[:i] + s[i + 1:], i, lremove - 1, rremove)
# 尝试去掉一个右括号
if rremove > 0 and s[i] == ')':
helper(s[:i] + s[i + 1:], i, lremove, rremove - 1)
helper(s, 0, lremove, rremove)
return res
示例推演
以 s = "()())()" 为例：
第一步：统计
- 遍历后：lremove=0, rremove=1
第二步：回溯
- 需要删除 1 个右括号
- 尝试删除位置 4 的
)："()()()"-> isValid=True -> 加入结果 - 尝试删除位置 6 的
)："()())("-> isValid=False
以 s = "(a)())()" 为例：
第一步：统计
- lremove=0, rremove=1
第二步：回溯
- 尝试删除位置 4 的
)："(a)()()"-> isValid=True - 尝试删除位置 5 的
)："(a())()"-> isValid=True
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力枚举 | O(2^n * n) | O(2^n) | 枚举所有子集并验证 |
| BFS | O(n * C(n,k)) | O(C(n,k)) | k为最少删除数 |
| 回溯（最优） | O(2^n) | O(n) | 剪枝后实际更快 |
易错点总结
1. 跳过连续相同字符
错误：不跳过连续相同的括号，导致重复结果。
正确：if i > start and s[i] == s[i - 1]: continue
原因：连续相同的括号删除任意一个效果相同，只需要尝试第一个。
2. 统计括号数
lremove 和 rremove 的统计要正确：遇到 ')' 时，优先尝试匹配之前的 '('。
3. 只删除括号
不要删除字母！检查 s[i] == '(' or s[i] == ')' 后再删除。
扩展思考
1. 如果只要求一个结果？
可以用栈找到不匹配的括号位置，直接删除即可。
2. 如果要求最少删除数？
回溯和BFS都能保证，因为它们都是按删除数递增的顺序尝试。