问题描述
来源：LeetCode第301题
难度：困难
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()"
输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
提示：
1 <= s.length <= 25
s 由小写英文字母以及括号 '(' 和 ')' 组成
s 中至多含 20 个括号
问题分析
这题是让删除最小数量的无效括号之后剩下的都是有效的，一提到最小最短等，除了动态规划以外，我们还要考虑能不能使用BFS，很显然这题是可以的。很多时候无论是bfs和还是dfs我们实际上都是可以把它想象为一棵树的。比如这题，每个节点的子节点都比父节点少一个字符，然后我们一层一层的判断每个节点的字符串是否有效，如果有效我们只需要把当前层所有的节点都访问完就不要往下访问了，因为当前层出现了有效的括号，他肯定是删除最少的，我们来画个图看下：
因为这里只有小括号，判断括号是否有效我们只需要统计左括号和右括号的数量即可，一个有效的括号必定是左括号的数量等于右括号的数量，并且在任何位置左括号的数量都不能小于右括号的数量，否则就是无效的，我们来看下判断方法
// 判断括号是否有效，如果是有效的括号，最终他的左括号数量和右括号数量
// 一定是相等的，并且在任何位置左括号的数量一定不能小于右括号的数量
private boolean isValid(String str) {
int count = 0;
for (char ch : str.toCharArray()) {
if (ch == '(') {// 遇到左括号加1
count++;
} else if (ch == ')') {
// 遇到右括号减1，如果count为负，说明右括号的
// 数量比左括号多，是无效的。
if (--count < 0)
return false;
}
}
return count == 0;
}
我们再来看下这题的最终代码
public List<String> removeInvalidParentheses(String s) {
List<String> res = new ArrayList<>();// 存储返回的结果值
Queue<String> queue = new LinkedList<>();// 存储每层的字符串
Set<String> set = new HashSet<>();// 存储子串，主要用来去重的
set.add(s);// 先把字符串 s 添加到集合 set 和队列 queue 中
queue.add(s);
while (!queue.isEmpty()) {
int levelCount = queue.size();// 每一层的字符串数量
for (int i = 0; i < levelCount; i++) {
String str = queue.poll();// 当前层的字符串出队
if (isValid(str)) // 当前字符串是否是有效的括号
res.add(str);
// 如果当前层出现了有效的字符串，而他的下一层字符串长度只会比他小，所以当
// 出现有效字符串的时候他的下一层我们不需要在判断，否则我们就继续判断
if (res.isEmpty()) {
for (int j = 0; j < str.length(); j++) {
// 下一层的字符串，遇到左括号或右括号要删除一个
if (str.charAt(j) == '(' || str.charAt(j) == ')') {
// 截取，每次只删除字符串 str 中的一个字符
String subStr = str.substring(0, j) + str.substring(j + 1);
// 这里主要是过滤掉重复的，如果集合set中存在字符串subStr，
// add的时候会返回false，否则会返回true
if (set.add(subStr))// 如果没有重复的就把字符串 subStr 添加到队列中
queue.offer(subStr);
}
}
}
}
// 如果当前层出现了有效括号，他们肯定是最长有效的，直接返回
if (res.size() > 0)
return res;
}
return res;
}联系客服
