LeetCode 题解工作台
删除无效的括号
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。 返回所有可能的结果。答案可以按 任意顺序 返回。 示例 1： 输入： s = "()())()" 输出： ["(())()","()()()"] 示例 2： 输入： s = "(a)())()" 输出： ["…
3
题型
4
代码语言
3
相关题
当前训练重点
困难 · 回溯·pruning
答案摘要
我们首先处理得到字符串 待删除的左、右括号的最小数量，分别记为 和 。 然后我们设计一个递归函数 `dfs(i, l, r, lcnt, rcnt, t)`，其中：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()" 输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()" 输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
提示：
1 <= s.length <= 25s由小写英文字母以及括号'('和')'组成s中至多含20个括号
解题思路
方法一：DFS + 剪枝
我们首先处理得到字符串 待删除的左、右括号的最小数量，分别记为 和 。
然后我们设计一个递归函数 dfs(i, l, r, lcnt, rcnt, t)，其中：
i表示当前处理到字符串 的第 个字符；l和r分别表示剩余待删除的左、右括号的数量；t表示当前得到的字符串；lcnt和rcnt分别表示当前得到的字符串中左、右括号的数量。
递归函数的逻辑如下：
- 如果
i等于字符串 的长度，且l和r都等于 ，则将t加入答案数组中； - 如果剩余的待处理字符数 小于剩余待删除的左右括号数量 ，或者当前得到的字符串中的左括号数量小于右括号数量，直接返回；
- 如果当前字符是左括号，我们可以选择删除或者保留，如果删除，需要满足 ，然后递归调用
dfs(i+1, l-1, r, lcnt, rcnt, t)； - 如果当前字符是右括号，我们可以选择删除或者保留，如果删除，需要满足 ，然后递归调用
dfs(i+1, l, r-1, lcnt, rcnt, t)； - 如果选择保留当前字符，我们需要判断当前字符是左括号、右括号还是字母。如果是左括号，我们需要更新
lcnt，如果是右括号，我们需要更新rcnt，然后递归调用dfs(i+1, l, r, lcnt, rcnt, t+s[i])。
我们调用 dfs(0, l, r, 0, 0, "")，搜索所有可能的字符串。
最后返回去重后的答案数组即可。
时间复杂度 ，空间复杂度 。长度为 的字符串有 种可能的删除方式，每种删除方式需要 的时间复制字符串。因此总时间复杂度为 。
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
def dfs(i, l, r, lcnt, rcnt, t):
if i == n:
if l == 0 and r == 0:
ans.add(t)
return
if n - i < l + r or lcnt < rcnt:
return
if s[i] == '(' and l:
dfs(i + 1, l - 1, r, lcnt, rcnt, t)
elif s[i] == ')' and r:
dfs(i + 1, l, r - 1, lcnt, rcnt, t)
dfs(i + 1, l, r, lcnt + (s[i] == '('), rcnt + (s[i] == ')'), t + s[i])
l = r = 0
for c in s:
if c == '(':
l += 1
elif c == ')':
if l:
l -= 1
else:
r += 1
ans = set()
n = len(s)
dfs(0, l, r, 0, 0, '')
return list(ans)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is exponential in the number of parentheses due to exploring all removal combinations, but pruning and BFS early termination reduce the practical runtime. Space complexity is proportional to the number of unique states and recursion or BFS queue size. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Looking for minimal removal and correctness rather than brute-force generation
- question_mark
Expect recognition of backtracking with pruning and BFS level-order exploration
- question_mark
Wants handling of duplicates and validation logic efficiently
常见陷阱
外企场景- error
Failing to prune branches exceeding minimal removals increases runtime
- error
Not handling duplicate strings leads to redundant results
- error
Incorrect validation of parentheses causes invalid strings in output
进阶变体
外企场景- arrow_right_alt
Only remove '(' or only ')' to balance a string
- arrow_right_alt
Return count of valid strings instead of actual strings
- arrow_right_alt
Input contains additional characters like digits or special symbols