05 August 2008
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 ).
Example 1:
1
2
Input: "()())()"
Output: ["()()()", "(())()"]
Example 2:
1
2
Input: "(a)())()"
Output: ["(a)()()", "(a())()"]
Example 3:
1
2
Input: ")("
Output: [""]
移除最少的括号使得给定字符串为一个合法的含有括号的字符串，也就是字符串中的左右括号数应该相同，而且每个右括号的左边一定有其对应的左括号，需要找出所有合法的取法。用BFS或者DFS来解：
1）BFS，参考这里，对于字符串s，通过移除一个括号产生所有的状态，检查移除后是否还valid，如果检查到了valid，那就把该状态加入到结果集中，完成；否则把状态加入到queue中并移除两个再检查，以此类推。这样BFS的好处是被移除的括号总是最少的，并且没有递归调用。时间复杂度O(n)，空间复杂度O(n^2)；
2）DFS，我们知道如何使用stack检查括号中的字符串是否有效，或更简单的使用counter。 counter在遇到”(“时将增加，在遇到“)“时将减少。每当计数器为负数时，前缀中的’）’就会大于”(“。
为了使prefix有效，我们需要删除“)”。问题是删除哪个？答案是prefix中的任何一个。但是，如果删除任何一个，将生成重复的结果，例如：s =())，我们可以删除s [1]或s [2]，但结果是相同的”()“。因此，我们限制只删除一系列连续的）中的第一个”)“。
删除第一个”)“后，prefix变得valid。然后，我们递归调用该函数以解决字符串的其余部分。但是，我们需要保留其他信息：”)“上一个移除位置。如果没有这个信息，我们通过上面步骤（仅以不同的顺序）删除两个“)”，就会产生重复项。 为此，我们会跟踪上一个移除”)“的位置，然后移除现在需移除的“)”。
那”(“该怎么处理呢呢？如果s =”(()((())“，我们需要删除’(‘呢？ 答案是：从右到左遍历做同样的事情，当然也可以reverse字符串然后重用上面的代码。
BFS
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> result = new ArrayList<>();
if (s == null) {
return result;
}
Set<String> visited = new HashSet<>(); // 记录BFS中产生的状态的字符串
Queue<String> queue = new LinkedList<>();//存储BFS中每一层的元素
//初始化
visited.add(s);
queue.add(s);
boolean found = false;//在某个level是否发现valid的状态
while (!queue.isEmpty()) {
s = queue.poll();
if (isValid(s)) {
//找到一个答案，加入到结果集
result.add(s);
found = true;
}
if (found) {//当前状态已加入结果集，跳出当前循环，检查下一个状态
continue;
}
//产生所有的状态
for (int i = 0; i < s.length(); i++) {
//只移除左括号或右括号，字母什么的不移除
if (s.charAt(i) != '(' && s.charAt(i) != ')') {
continue;
}
//产生一个临时状态
String temp = s.substring(0, i) + s.substring(i + 1);//为什么这里i + 1不会越界？
if (!visited.contains(temp)) {
queue.add(temp);
visited.add(temp);
}
}
}
return result;
}
//检查当前状态是否valid，也可以用stack来做，不过需要额外空间
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;
}
}
DFS
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
class Solution {
public static List<String> removeInvalidParentheses(String s) {
List<String> result = new ArrayList<>();
char[] check = new char[]{'(', ')'};
dfs(s, result, check, 0, 0);
return result;
}
public static void dfs(String s, List<String> result, char[] check, int last_i, int last_j) {
int count = 0; // 从左到右记录左括号
int i = last_i;
while (i < s.length() && count >= 0) {
if (s.charAt(i) == check[0]) count++; // 左括号，累加
if (s.charAt(i) == check[1]) count--; // 右括号，累减
i++;
}
if (count >= 0) { // 到这里没有额外的')'，现在通过翻转字符串开始检查有没有额外的'(' - 翻转过来复用代码
String reversed = new StringBuffer(s).reverse().toString();
if (check[0] == '(') {
dfs(reversed, result, new char[]{')', '('}, 0, 0);
} else {
result.add(reversed);
}
} else { // 有额外的 ')'，进行处理
i -= 1; // 'i-1'是多出来的')' 让count < 0的地方
for (int j = last_j; j<= i; j++) {
if (s.charAt(j) == check[1] && (j == last_j || s.charAt(j-1) != check[1])) {
dfs(s.substring(0, j) + s.substring(j + 1, s.length()), result, check, i, j);
}
}
}
}
}