题目：
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note: The input string may contain letters other than the parentheses ( and ).
Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]
链接： http://leetcode.com/problems/remove-invalid-parentheses/
题解：
给定String，去除invalid括号，输出所有结果集。一开始想的是DFS + Backtracking，没有坚持下去。后来在Discuss里发现了jeantimex大神的BFS方法非常好，于是搬过来借鉴。方法是我们每次去掉一个"("或者")"，然后把新的string加入到Queue里，继续进行计算。要注意的是需要设置一个boolean foundResult，假如在这一层找到结果的话，我们就不再继续进行下面的for循环了。这里应该还可以继续剪枝一下，比如记录当前这个结果的长度len，当queue里剩下的string长度比这个len小的话，我们不进行验证isValid这一步。
Time Complexity - O(n * 2)， Space Complexity - O(2)
public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> res = new ArrayList<>();
if(s == null) {
return res;
}
Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.offer(s);
boolean foundResult = false;
while(!queue.isEmpty()) {
s = queue.poll();
if(isValid(s)) {
res.add(s);
foundResult = true;
}
if(foundResult) {
continue;
}
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(c == '(' || c == ')') {
String t = s.substring(0, i) + s.substring(i + 1);
if(!visited.contains(t)) {
queue.offer(t);
visited.add(t);
}
}
}
}
return res;
}
private boolean isValid(String s) {
int leftCount = 0;
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(c == '(') {
leftCount++;
} else if (c == ')') {
leftCount--;
}
if(leftCount < 0) {
return false;
}
}
return leftCount == 0;
}
}Reference:
https://leetcode.com/discuss/67842/share-my-java-bfs-solution
https://leetcode.com/discuss/67853/my-c-dfs-solution-16ms
https://leetcode.com/discuss/67919/java-optimized-dfs-solution-3-ms
https://leetcode.com/discuss/67861/short-python-bfs
https://leetcode.com/discuss/72208/easiest-9ms-java-solution
https://leetcode.com/discuss/67861/short-python-bfs
https://leetcode.com/discuss/72208/easiest-9ms-java-solution
https://leetcode.com/discuss/67908/java-bfs-solution-16ms-avoid-generating-duplicate-strings
https://leetcode.com/discuss/67821/and-bfs-java-solutions-add-more-optimized-fast-dfs-solution
https://leetcode.com/discuss/68038/clean-java-solution-bfs-optimization-40ms
https://leetcode.com/discuss/68010/fast-optimized-dfs-java-solution