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())()"]
")(" -> [""]
Credits:
Special thanks to @hpplayer for adding this problem and creating all test cases.
Subscribe to see which companies asked this question
思路：
BFS
java code:
public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> ans = new ArrayList<>();
if(s == null) return ans;
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
queue.offer(s);
boolean found = false;
while(!queue.isEmpty()) {
String tmp = queue.poll();
if(isValid(tmp)) {
ans.add(tmp);
found = true;
}
if(found) continue;
for(int i = 0;i < tmp.length();i++) { //将各个（去掉i字符的）子串入队
if(tmp.charAt(i) != '(' && tmp.charAt(i) != ')') continue;
String sub = tmp.substring(0,i) + tmp.substring(i+1);
if(!visited.contains(sub)) {
queue.offer(sub);
visited.add(sub);
}
}
}
return ans;
}
// 自定义函数：检查是否合法
boolean isValid(String s) {
int count = 0;
for(int i=0;i<s.length();i++) {
char c = s.charAt(i);
if(c == '(') count++;
if(c == ')') {
if(count==0) return false;
count--;
}
}
return count == 0;
}
}LeetCode:Remove Invalid Parentheses
原文：http://blog.csdn.net/itismelzp/article/details/51685770