删除无效的括号
问题简介
给你一个由若干括号和字母组成的字符串 s，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按任意顺序返回。
示例说明
示例 1：
- 输入：
s = "()())()" - 输出：
["(())()","()()()"]
示例 2：
- 输入：
s = "(a)())()" - 输出：
["(a())()","(a)()()"]
示例 3：
- 输入：
s = ")(" - 输出：
[""]
解题思路
方法一：BFS（广度优先搜索）
核心思想：由于要求删除最少数量的括号，BFS 天然适合解决最短路径/最少操作类问题。
步骤分解：
- 初始化：将原始字符串加入队列
- 层级遍历：
- 对于当前层级的所有字符串，检查是否有效
- 如果找到有效字符串，直接返回该层级所有有效结果（因为 BFS 保证了最少删除）
- 如果没有有效字符串，生成下一层级的所有可能（删除一个括号）
- 去重：使用 Set 避免重复处理相同字符串
- 有效性检查：通过计数器验证括号匹配
方法二：DFS + 剪枝
核心思想：先计算需要删除的左右括号数量，然后通过 DFS 枚举所有可能的删除方案。
步骤分解：
- 预处理：计算需要删除的左括号
leftRemove和右括号rightRemove数量 - DFS 回溯：
- 遍历字符串每个字符
- 对于左括号：可以选择保留或删除（如果还有删除配额）
- 对于右括号：可以选择保留或删除（如果还有删除配额），但保留时需要确保不会造成右括号过多
- 对于其他字符：直接保留
- 剪枝优化：
- 提前计算删除数量，避免无效搜索
- 在构建过程中实时检查有效性
方法三：递归枚举（暴力法）
虽然可行，但时间复杂度过高，不推荐在实际面试中使用。
代码实现
// Java 实现 - BFS 方法
import java.util.*;
public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> result = <>();
Queue<String> queue = <>();
Set<String> visited = <>();
queue.offer(s);
visited.add(s);
;
(!queue.isEmpty() && !found) {
queue.size();
( ; i < size; i++) {
queue.poll();
(isValid(current)) {
result.add(current);
found = ;
}
(found) ;
( ; j < current.length(); j++) {
current.charAt(j);
(c != && c != ) ;
current.substring(, j) + current.substring(j + );
(!visited.contains(next)) {
queue.offer(next);
visited.add(next);
}
}
}
}
result;
}
{
;
( c : s.toCharArray()) {
(c == ) {
count++;
} (c == ) {
count--;
(count < ) ;
}
}
count == ;
}
}
