-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_301.java
More file actions
103 lines (96 loc) · 3.38 KB
/
Copy pathP_301.java
File metadata and controls
103 lines (96 loc) · 3.38 KB
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package leetcode.hard;
import java.util.ArrayList;
import java.util.List;
public class P_301 {
int min = Integer.MAX_VALUE;
public List<String> removeInvalidParentheses(String s) {
final List<String> res = new ArrayList<>();
dfs(s, new StringBuilder(), 0, 0, 0, 0, res);
return new ArrayList<>(res);
}
private void dfs(String s, StringBuilder sb, int open, int close, int delete, int idx, List<String> res) {
if (s.length() == idx) {
if (open == close) {
if (min > delete) {
res.clear();
min = delete;
}
if (min == delete) {
res.add(new String(sb));
}
}
return;
}
final char c = s.charAt(idx);
if (c == '(') {
dfs(s, sb, open, close, delete + 1, idx + 1, res);
sb.append('(');
dfs(s, sb, open + 1, close, delete, idx + 1, res);
sb.deleteCharAt(sb.length() - 1);
} else if (c == ')') {
if (open > close) {
sb.append(')');
dfs(s, sb, open, close + 1, delete, idx + 1, res);
sb.deleteCharAt(sb.length() - 1);
}
dfs(s, sb, open, close, delete, idx + 1, res);
} else {
sb.append(c);
dfs(s, sb, open, close, delete + 1, idx + 1, res);
sb.deleteCharAt(sb.length() - 1);
}
}
public List<String> removeInvalidParenthesesLVP(String s) {
int delLeft = 0;
int delRight = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
delLeft++;
} else if (c == ')') {
if (delLeft > 0) {
delLeft--;
} else {
delRight++;
}
}
}
final List<String> res = new ArrayList<>();
recurse(s, new StringBuilder(), delLeft, delRight, 0, 0, res);
return res;
}
private static void recurse(String s, StringBuilder sb, int open, int close, int delete, int idx,
List<String> res) {
if (idx == s.length() && delete == 0 && open == 0 && close == 0) {
res.add(sb.toString());
return;
}
if (delete < 0 || open < 0 || close < 0 || idx == s.length()) {
return;
}
final int len = sb.length();
final char c = s.charAt(idx);
if (c == '(') {
recurse(s, sb, open - 1, close, delete, idx + 1, res);
int rep = 1;
while (idx + rep < s.length() && s.charAt(idx + rep) == '(') {
rep++;
}
sb.append(s.toCharArray(), idx, rep);
recurse(s, sb, open, close, delete + rep, idx + rep, res);
sb.setLength(len);
} else if (c == ')') {
recurse(s, sb, open, close - 1, delete, idx + 1, res);
int rep = 1;
while (idx + rep < s.length() && s.charAt(idx + rep) == ')') {
rep++;
}
sb.append(s.toCharArray(), idx, rep);
recurse(s, sb, open, close, delete - rep, idx + rep, res);
sb.setLength(len);
} else {
sb.append(c);
recurse(s, sb, open, close, delete, idx + 1, res);
sb.deleteCharAt(len);
}
}
}