1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 | public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> result = new ArrayList<String>();
HashSet<String> lookup = new HashSet<String>();
Queue<String> queue = new LinkedList<String>();
queue.add(s);
queue.add(null);
while (!queue.isEmpty()){
String current = queue.poll();
if (current == null){
if (result.size() != 0) break;
queue.add(null);
}
if (current != null && !lookup.contains(current)){
lookup.add(current);
if (isValid(current)) result.add(current);
else{
for (int i = 0; i < current.length(); i++){
char temp = current.charAt(i);
if (temp == '(' || temp == ')'){
queue.add(current.substring(0,i)+current.substring(i+1));
}
}
}
}
}
return result;
}
private boolean isValid(String s){
int count = 0;
for (int i = 0; i < s.length(); i++){
char current = s.charAt(i);
if (current == '(') count++;
else if (current == ')') count--;
if (count < 0) return false;
}
return count == 0;
}
}
|
No comments:
Post a Comment