LeetCode 301. 删除无效的括号
题目描述
思路分析
解法一：BFS 逐层删除（推荐）
核心思路：
- 要求删除最少数量的括号，BFS 天然按”删除次数”逐层扩展，第一次找到合法结果时，所用删除次数必然最少（最短路径语义）。
- 将原始字符串加入队列，用 HashSet 去重，避免重复处理同一个字符串。
- 对当前层的每个字符串，尝试删除每一个括号字符（
'('或')'），生成下一层候选串，非括号字符直接跳过。- 若当前层出现合法串，收集该层所有合法结果后立即返回，不再继续向下删除。
- 合法性检查：用计数器
count，遇'('加 1，遇')'减 1；count < 0立即返回false，遍历完后count == 0则合法。
复杂度分析：
- 时间复杂度：O(n × 2ⁿ)，其中 n 表示字符串长度，最坏情况下每层枚举所有括号位置
- 空间复杂度：O(n × 2ⁿ)，其中 n × 2ⁿ 表示队列中存储的所有候选字符串总长度
class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> res = new ArrayList<>();
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
queue.offer(s);
visited.add(s);
// 标记是否已在当前层找到合法结果
boolean found = false;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String cur = queue.poll();
if (isValid(cur)) {
res.add(cur);
found = true;
}
// 当前层未找到合法结果，继续生成下一层候选串
if (!found) {
for (int j = 0; j < cur.length(); j++) {
if (cur.charAt(j) != '(' && cur.charAt(j) != ')') {
continue;
}
String next = cur.substring(0, j) + cur.substring(j + 1);
if (!visited.contains(next)) {
visited.add(next);
queue.offer(next);
}
}
}
}
// 当前层找到合法结果，整层处理完毕后立即返回
if (found) {
break;
}
}
return res.isEmpty() ? Collections.singletonList("") : res;
}
private boolean isValid(String s) {
int count = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
count++;
} else if (c == ')') {
count--;
// 右括号多于左括号，立即返回无效
if (count < 0) {
return false;
}
}
}
return count == 0;
}
}
func removeInvalidParentheses(s string) []string {
// 检查字符串是否为合法括号序列
isValid := func(str string) bool {
count := 0
for _, c := range str {
if c == '(' {
count++
} else if c == ')' {
count--
// 右括号多于左括号，立即返回无效
if count < 0 {
return false
}
}
}
return count == 0
}
visited := map[string]bool{s: true}
queue := []string{s}
var res []string
// 标记是否已在当前层找到合法结果
found := false
for len(queue) > 0 && !found {
nextQueue := []string{}
for _, cur := range queue {
if isValid(cur) {
res = append(res, cur)
found = true
}
// 当前层未找到合法结果，继续生成下一层候选串
if !found {
for i := 0; i < len(cur); i++ {
if cur[i] != '(' && cur[i] != ')' {
continue
}
next := cur[:i] + cur[i+1:]
if !visited[next] {
visited[next] = true
nextQueue = append(nextQueue, next)
}
}
}
}
queue = nextQueue
}
if len(res) == 0 {
return []string{""}
}
return res
}
解法二：DFS 回溯剪枝
核心思路：
- 预处理：先扫描一遍，统计需要删除的多余左括号数
leftRem和多余右括号数rightRem。
- 遇
'('：leftRem++- 遇
')'：若leftRem > 0则leftRem--（被一个(匹配消掉）；否则rightRem++- DFS 从左到右枚举，对每个位置的括号决定是否删除：删除时递减对应计数，保留时直接递归。
- 剪枝：
leftRem < 0 || rightRem < 0时停止；递归到末尾时leftRem == 0 && rightRem == 0才收集结果。- 为避免同位置同字符重复删除，跳过与前一个相同字符的重复处理。
复杂度分析：
- 时间复杂度：O(n × 2ⁿ)，其中 n 表示字符串长度，最坏情况下每个括号都有删/留两种选择
- 空间复杂度：O(n)，其中 n 表示递归调用栈的深度
class Solution {
private List<String> res = new ArrayList<>();
public List<String> removeInvalidParentheses(String s) {
// 预处理：统计需要删除的多余左括号数和右括号数
int leftRem = 0, rightRem = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
leftRem++;
} else if (c == ')') {
if (leftRem > 0) {
leftRem--;
} else {
rightRem++;
}
}
}
dfs(s, 0, leftRem, rightRem, new StringBuilder());
return res;
}
private void dfs(String s, int index, int leftRem, int rightRem, StringBuilder path) {
// 处理完所有字符，且恰好删够了多余括号
if (index == s.length()) {
if (leftRem == 0 && rightRem == 0) {
res.add(path.toString());
}
return;
}
char c = s.charAt(index);
// 尝试删除当前括号字符（剪枝：只有还需要删时才删）
if (c == '(' && leftRem > 0) {
dfs(s, index + 1, leftRem - 1, rightRem, path);
}
if (c == ')' && rightRem > 0) {
dfs(s, index + 1, leftRem, rightRem - 1, path);
}
// 保留当前字符
path.append(c);
// 剪枝：当前路径中右括号已多于左括号，无法构成合法串
int len = path.length();
int balance = 0;
boolean valid = true;
for (int i = 0; i < len; i++) {
if (path.charAt(i) == '(') {
balance++;
} else if (path.charAt(i) == ')') {
balance--;
}
if (balance < 0) {
valid = false;
break;
}
}
if (valid) {
dfs(s, index + 1, leftRem, rightRem, path);
}
path.deleteCharAt(path.length() - 1);
}
}
func removeInvalidParentheses(s string) []string {
// 预处理：统计需要删除的多余左括号数和右括号数
leftRem, rightRem := 0, 0
for _, c := range s {
if c == '(' {
leftRem++
} else if c == ')' {
if leftRem > 0 {
leftRem--
} else {
rightRem++
}
}
}
var res []string
var dfs func(index, leftRem, rightRem int, path []byte)
dfs = func(index, leftRem, rightRem int, path []byte) {
// 处理完所有字符，且恰好删够了多余括号
if index == len(s) {
if leftRem == 0 && rightRem == 0 {
res = append(res, string(path))
}
return
}
c := s[index]
// 尝试删除当前括号字符（剪枝：只有还需要删时才删）
if c == '(' && leftRem > 0 {
dfs(index+1, leftRem-1, rightRem, path)
}
if c == ')' && rightRem > 0 {
dfs(index+1, leftRem, rightRem-1, path)
}
// 保留当前字符，检查当前路径是否仍合法（右括号未超过左括号）
newPath := append(path, c)
balance := 0
valid := true
for _, ch := range newPath {
if ch == '(' {
balance++
} else if ch == ')' {
balance--
}
// 当前路径右括号已多于左括号，剪枝
if balance < 0 {
valid = false
break
}
}
if valid {
dfs(index+1, leftRem, rightRem, newPath)
}
}
dfs(0, leftRem, rightRem, []byte{})
if len(res) == 0 {
return []string{""}
}
return res
}
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 20. 有效的括号 | 简单 | 栈 |
| 22. 括号生成 | 中等 | 回溯 |
| 32. 最长有效括号 | 困难 | 动态规划、栈 |
| 1249. 移除无效的括号 | 中等 | 栈 |
| 678. 有效的括号字符串 | 中等 | 栈、贪心 |
| 856. 括号的分数 | 中等 | 栈 |
| 921. 使括号有效的最少添加 | 中等 | 贪心 |
| 1003. 检查替换后的词是否有效 | 中等 | 栈 |
| 2116. 判断一个括号字符串是否有效 | 中等 | 贪心 |
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！