LeetCode 301. 删除无效的括号
目录
题目描述
题意分析
输入是一个由小写字母和圆括号混合而成的字符串，要求删掉尽可能少的括号字符，使剩下的串括号匹配合法，并返回所有能达到这个最少删除数的不同结果。合法的定义是：从左往右扫描时右括号数量任何时刻都不超过左括号数量，且扫描结束时两者相等。
题面里藏着三个关键信号。第一，删除的对象只能是括号，字母必须原样保留在原位置，这直接决定了搜索时可以跳过所有字母。第二，要的不是任意一个解，而是全部最优解，所以不能找到一个就返回，必须把同一「删除数量」下的所有合法串都收齐。第三，结果集要去重，
"()())()"删掉第 $3$ 个和第 $4$ 个字符会得到同一个串，只能算一个。规模上，字符串长度不超过 $25$，其中括号最多 $20$ 个，这个量级明确允许指数级的枚举，是在暗示可以直接搜索所有删除方案，不必去构造精巧的线性算法。
边界包括：本身已经合法的串，答案就是它自己，删除数为 $0$；完全没有括号的串（如
"abc"），同样直接返回原串；以及全是不可能匹配的括号（如")("），最终会一路删到空串""，空串是合法的，必须作为答案返回而不是漏掉。
解法：BFS 按删除次数分层
核心思路
把字符串看成状态，每次删掉一个括号就是走一条边。BFS 的第 $d$ 层恰好包含删除 $d$ 个括号后得到的所有不同字符串，因此第一次出现合法字符串的层，就是最少删除层。
找到一个合法状态后不能立刻结束：题目要求返回全部答案，必须检查完整个当前层；一旦本层收集到答案，就不再生成下一层。
visited保证同一字符串只入队一次，连续相同括号只尝试删除第一个，还能避免构造明显重复的状态。不变量：进入每轮循环时，
level中的字符串互不相同，并且都恰好删除了相同数量的括号。按层完整检查保证最优性与完备性；合法性则用余额balance判断——任意前缀不能为负，最终必须为零。
解题步骤
- 第 $0$ 层只放原字符串，并加入
visited。- 先检查当前层的每个字符串；若存在合法串，返回本层所有合法结果。
- 若本层无解，枚举每个字符串中的括号位置，删除一个括号生成下一层；字母不能删除。
- 跳过连续重复括号产生的等价删除，并用
visited做全局去重。- 判断合法性时，遇
(加一、遇)减一；余额变负立即失败，扫描结束余额为零才合法。以
"()())()"为例：第 $0$ 层不合法；第 $1$ 层包含"(())()"与"()()()"两个合法串。由于这是首次出现合法串的层，两者都是且仅是最少删除答案。
代码实现
class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> level = new ArrayList<>();
level.add(s);
Set<String> visited = new HashSet<>();
visited.add(s);
while (!level.isEmpty()) {
List<String> answer = new ArrayList<>();
for (String cur : level) {
if (isValid(cur)) {
answer.add(cur);
}
}
if (!answer.isEmpty()) {
return answer;
}
List<String> nextLevel = new ArrayList<>();
for (String cur : level) {
for (int i = 0; i < cur.length(); i++) {
char ch = cur.charAt(i);
if (ch != '(' && ch != ')') {
continue;
}
if (i > 0 && ch == cur.charAt(i - 1)) {
continue;
}
String next = cur.substring(0, i) + cur.substring(i + 1);
if (visited.add(next)) {
nextLevel.add(next);
}
}
}
level = nextLevel;
}
return new ArrayList<>();
}
private boolean isValid(String s) {
int balance = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(') {
balance++;
} else if (ch == ')') {
balance--;
if (balance < 0) {
return false;
}
}
}
return balance == 0;
}
}
func removeInvalidParentheses(s string) []string {
visited := map[string]bool{s: true}
level := []string{s}
for len(level) > 0 {
answer := make([]string, 0)
for _, cur := range level {
if isValidParentheses(cur) {
answer = append(answer, cur)
}
}
if len(answer) > 0 {
return answer
}
nextLevel := make([]string, 0)
for _, cur := range level {
for i := 0; i < len(cur); i++ {
if cur[i] != '(' && cur[i] != ')' {
continue
}
if i > 0 && cur[i] == cur[i-1] {
continue
}
next := cur[:i] + cur[i+1:]
if !visited[next] {
visited[next] = true
nextLevel = append(nextLevel, next)
}
}
}
level = nextLevel
}
return nil
}
func isValidParentheses(s string) bool {
balance := 0
for i := 0; i < len(s); i++ {
if s[i] == '(' {
balance++
} else if s[i] == ')' {
balance--
if balance < 0 {
return false
}
}
}
return balance == 0
}
复杂度分析
设字符串长度为 $n$，其中有 $p$ 个括号。
- 时间复杂度：最坏 $O(pn \cdot 2^p)$，可简写为 $O(n^2 \cdot 2^p)$。状态数至多为 $2^p$；每个状态最多尝试删除 $p$ 个括号，构造和哈希新字符串需要 $O(n)$。实际搜索在最少删除层提前结束。
- 空间复杂度：$O(n \cdot 2^p)$，
visited、当前层和下一层最多保存指数级字符串，每个字符串长度为 $O(n)$。
关键点总结
- 等权最少操作问题可以建模为最短路；BFS 层数就是删除次数。
- 「全部最优解」要求检查完整个首个合法层，不能找到一个就停。
- 连续重复括号去重只消除同一父状态的等价选择，
visited则消除不同路径得到的相同状态。- 回溯也能先统计必须删除的左右括号数，再按配额搜索；BFS 的优势是最少删除证明更直接。
易错点总结
- 找到首个合法串就返回：会漏掉同层的其他答案，如
"()())()"还应得到"(())()"和"()()()"。- 合法性只检查最终余额：
")("最终为零，但前缀已经非法；必须在余额变负时立即失败。- 删除字母：题目只允许删除括号，字母及其相对顺序必须保留。
- 不去重：不同删除顺序会反复生成同一字符串，既产生重复答案，也会放大搜索规模。
- 跳过第 $0$ 层：本身合法的输入应原样返回，删除次数为零。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 20. 有效的括号 | 简单 | 三种括号需用栈匹配，单计数器不再够用 |
| 22. 括号生成 | 中等 | 反过来构造全部合法串，靠左右配额剪枝 |
| 32. 最长有效括号 | 困难 | 求最长合法子串长度，用动态规划或栈存下标 |
| 678. 有效的括号字符串 | 中等 | 引入通配符 *，需维护计数器的可行区间 |
| 1249. 移除无效的括号 | 中等 | 只要求任意一个最优解，两遍扫描即可，无需搜索 |
| 1614. 括号的最大嵌套深度 | 简单 | 保证输入合法，只需记录计数器的最大值 |