LeetCode 301. 删除无效的括号
题目描述
题意分析
只能删除括号，字母及剩余字符的相对顺序必须保留。要求先让删除数量最少，再返回这个最少删除数量下所有不同的合法字符串。
合法括号串要满足两点：从左到右的任意前缀中，右括号都不能多于左括号；扫描结束后，左右括号数量相等。字母不参与配对，空字符串也合法。
解法：BFS 按删除次数分层
核心思路
[!blue]
把每个字符串看成一个状态，删除其中一个括号就到达下一个状态。每次操作的代价都是
1，因此可以按删除次数做 BFS：第0层是原串，第d层保存恰好删除d个括号后得到的不同字符串。先检查当前层的全部状态。若这一层出现合法字符串，那么更浅的层已经检查过且都无解，当前删除次数就是最少的；同层的所有合法串都要收集，随后立即返回，不再向下一层删除。若当前层无解，才生成下一层。
合法性检查用
balance记录已经读到但尚未匹配的左括号数。遇到(加一，遇到)减一。若途中变负，说明这个右括号前面没有左括号可配对，后面的字符也无法补救；扫描结束时还必须为0，避免留下未匹配的左括号。删除过程有两种重复：同一段连续相同括号中删任意一个，得到的字符串相同，所以只枚举第一个；不同删除顺序也可能到达同一个字符串，用
visited只保留首次生成的状态。状态本身已经完整决定后续能删出什么，舍弃重复路径不会丢失答案。
解题步骤
- 将原串放入
level，同时加入visited，表示删除0次。- 遍历
level，用前缀余额检查合法性，把所有合法串加入answer。- 若
answer非空，返回整个列表；即使唯一答案是空字符串，列表仍然非空。- 否则枚举每个状态中的括号位置，跳过字母，以及与前一个字符相同的括号。
- 删除当前括号，拼接它前后的两段；只有
visited中尚不存在的新字符串才能加入nextLevel。- 用
nextLevel替换level，继续检查下一层。最迟删除全部括号后，剩下的字母串一定合法。
代码实现
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(n(p+1)2^p)$，状态至多 $2^p$ 个，每个状态做合法性扫描，并尝试至多
p次删除与字符串构造；即使没有括号也要检查原串。- 空间复杂度：$O(n2^p)$，保存访问集合及当前、下一层的字符串。
关键点总结
[!green]
- BFS 层数等于删除次数，首个存在合法状态的层给出最少删除次数。
- 在这一层收集全部合法状态，才能得到所有最优结果。
- 合法性由“任意前缀余额非负，最终余额为零”共同保证。
- 去重针对结果字符串，不同删除位置或顺序无需分别保留。
易错点总结
[!yellow]
- 不能找到第一个合法串就返回，否则会漏掉同层其他答案；也不能继续收集更深层的合法串，否则会混入非最少删除的结果。
- 只检查最终左右括号数量相等不够，右括号先出现也会造成非法前缀。
- 只能跳过连续相同括号的等价删除，不能把相同类型括号的所有删除位置都视为等价。
- 原串本就合法时应直接返回它，不能跳过第
0层。- 空字符串是一个合法结果，不能把包含空字符串的答案列表误判为无解。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1249. 移除无效的括号 | 中等 | 两题都最少删除括号，原题只需任意一个合法结果，本题要输出全部最优结果并去重。 |
| 22. 括号生成 | 中等 | 合法前缀的左右括号约束相同，原题从空串生成，本题只能从给定串中删除。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！