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())()"]
")(" -> [""]
一刷
題解：如果這個(gè)string不滿足條件该编，那么出去其中的一個(gè)char, 并全部入棧蹂季，如果是6個(gè)char的時(shí)候滿足條件，最終在隊(duì)列中只會(huì)是6個(gè)和5個(gè)char, 由于found此時(shí)已被置為ture,那么就不會(huì)再往隊(duì)列里面加入新的更短的字符串狡汉，可以保證Remove the minimum number
public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> res = new ArrayList<>();
if(s == null) return res;
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
//initialize
queue.add(s);
visited.add(s);
boolean found = false;
while(!queue.isEmpty()){
s = queue.poll();
if(isValid(s)){
res.add(s);
found = true;
}
if(found) continue;
//generate all possible states
for(int i=0; i<s.length(); i++){
if (s.charAt(i) != '(' && s.charAt(i) != ')') continue;
String t = s.substring(0, i) + s.substring(i+1);//remove the ith
if(!visited.contains(t)){
queue.add(t);
visited.add(t);
}
}
}
return res;
}
private 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 == ')' && count-- ==0) return false;
}
return count == 0;
}
}
