1. 题目

原题链接

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：

输入：s = “()())()”
输出：["(())()","()()()"]

示例 2：

输入：s = “(a)())()”
输出：["(a())()","(a)()()"]

示例 3：

输入：s = “)(”
输出：[""]

提示：

1 <= s.length <= 25
s 由小写英文字母以及括号 ‘(’ 和 ‘)’ 组成
s 中至多含 20 个括号

Related Topics 深度优先搜索 广度优先搜索
👍 444 👎 0

2. 题解

2.1 解法1: BFS

1. 每次只删除一个括号, 然后检查该层的括号是否合法, 若合法, 返回该层的所有括号即可
2. 上一层level和下一层level之间的关系为：把所有上一层level中的每个元素都拿出来，列举出在删除一个括号后的所有可能的情况。(不管删除以后是否合法），添加到下一个level中的元素。
3. 重复问题解决: 使用 set 去重
4. 检查括号合法性问题: 使用计数法

    public class Solution {public List<String> removeInvalidParentheses(String s) {List<String> ans = new ArrayList<>();Queue<String> queue = new LinkedList<>();Set<String> set = new HashSet<>();queue.offer(s);set.add(s);// 标志变量, 判断是否合法, 结束循环boolean flag = false;while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {String tempStr = queue.poll();if (isValid(tempStr)) {ans.add(tempStr);flag = true;}// 开始计算下一层, 即遍历删除一个括号for (int j = 0; j < tempStr.length(); j++) {if (tempStr.charAt(j) == '(' || tempStr.charAt(j) == ')') {// 删除下标为 j 的字符String nextStr = tempStr.substring(0, j) + tempStr.substring(j + 1);if (!set.contains(nextStr)) {queue.offer(nextStr);set.add(nextStr);}}}}// 每次计算完一层, 进行判断if (flag) {break;}}return ans;}public boolean isValid(String s) {int cnt = 0;char[] ss = s.toCharArray();for (int i = 0; i < ss.length; i++) {if (ss[i] == '(') {cnt++;} else if (ss[i] == ')') {cnt--;}if (cnt < 0) {return false;}}return cnt == 0;}}

参考:
BFS简单而又详细的python讲解
代码参考—官方题解

2.2 DFS

参考: 官方题解