301 Remove Invalid Parentheses

301. Remove Invalid Parentheses

1. Question

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:
1
"()())()" ->["()()()", "(())()"]
2
"(a)())()" ->["(a)()()", "(a())()"]
3
")(" ->[""]
Copied!

2. Implementation

(1) BFS
1
class Solution {
2
public List<String> removeInvalidParentheses(String s) {
3
List<String> res = new ArrayList<>();
4
5
Queue<String> queue = new LinkedList<>();
6
Set<String> visited = new HashSet<>();
7
8
queue.add(s);
9
visited.add(s);
10
11
boolean minLevel = false;
12
13
while (!queue.isEmpty()) {
14
String curStr = queue.remove();
15
16
if (isValid(curStr)) {
17
minLevel = true;
18
res.add(curStr);
19
}
20
21
if (minLevel) {
22
continue;
23
}
24
25
for (int i = 0; i < curStr.length(); i++) {
26
if (isParenthesis(curStr.charAt(i))) {
27
String nextStr = curStr.substring(0, i) + curStr.substring(i + 1);
28
29
if (!visited.contains(nextStr)) {
30
queue.add(nextStr);
31
visited.add(nextStr);
32
}
33
}
34
}
35
}
36
return res;
37
}
38
39
public boolean isParenthesis(char c) {
40
return c == '(' || c == ')';
41
}
42
43
public boolean isValid(String s) {
44
int count = 0;
45
for (int i = 0; i < s.length(); i++) {
46
if (s.charAt(i) == '(') {
47
++count;
48
}
49
else if (s.charAt(i) == ')') {
50
--count;
51
}
52
53
if (count < 0) {
54
return false;
55
}
56
}
57
return count == 0;
58
}
59
}
Copied!
(2) DFS
1
class Solution {
2
public List<String> removeInvalidParentheses(String s) {
3
int removableLeftParen = 0, removableRightParen = 0;
4
5
for (char c : s.toCharArray()) {
6
if (c == '(') {
7
++removableLeftParen;
8
}
9
else if (c == ')') {
10
if (removableLeftParen > 0) {
11
--removableLeftParen;
12
}
13
else {
14
++removableRightParen;
15
}
16
}
17
}
18
19
Set<String> res = new HashSet<>();
20
StringBuilder parens = new StringBuilder();
21
removeParenthesisByDFS(s, 0, removableLeftParen, removableRightParen, 0, parens, res);
22
return new ArrayList<>(res);
23
}
24
25
public void removeParenthesisByDFS(String s, int pos, int removableLeftParen, int removableRightParen, int open, StringBuilder parens, Set<String> res) {
26
if (removableLeftParen < 0 || removableRightParen < 0 || open < 0) {
27
return;
28
}
29
30
if (pos == s.length()) {
31
if (removableLeftParen == 0 && removableRightParen == 0 && open == 0) {
32
res.add(parens.toString());
33
}
34
return;
35
}
36
37
char c = s.charAt(pos);
38
int len = parens.length();
39
40
if (c == '(') {
41
// Remove it
42
removeParenthesisByDFS(s, pos + 1, removableLeftParen - 1, removableRightParen, open, parens, res);
43
// Use it
44
removeParenthesisByDFS(s, pos + 1, removableLeftParen, removableRightParen, open + 1, parens.append(c), res);
45
}
46
else if (c == ')') {
47
// Remove it
48
removeParenthesisByDFS(s, pos + 1, removableLeftParen, removableRightParen - 1, open, parens, res);
49
// Use it
50
removeParenthesisByDFS(s, pos + 1, removableLeftParen, removableRightParen, open - 1, parens.append(c), res);
51
}
52
else {
53
removeParenthesisByDFS(s, pos + 1, removableLeftParen, removableRightParen, open, parens.append(c), res);
54
}
55
56
parens.setLength(len);
57
}
58
}
Copied!

3. Time & Space Complexity

BFS: 时间复杂度: O(n * 2^n), isValid()需要花费O(n), 每个string的character有两种状态(remove/keep), 总共有2^n种状态,所以时间复杂度是O(n * 2^n), 空间复杂度O(2^n)
DFS: 时间复杂度: O(2^n), 空间复杂度O(2^n)