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())()"]
")(" -> [""]
一刷
题解:如果这个string不满足条件,那么出去其中的一个char, 并全部入栈,如果是6个char的时候满足条件,最终在队列中只会是6个和5个char, 由于found此时已被置为ture,那么就不会再往队列里面加入新的更短的字符串,可以保证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;
}
}