-
Notifications
You must be signed in to change notification settings - Fork 44
/
_301_removeInvalidParentheses.java
124 lines (100 loc) · 4.08 KB
/
_301_removeInvalidParentheses.java
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
package pp.arithmetic.leetcode;
import pp.arithmetic.Util;
import java.util.*;
/**
* Created by wangpeng on 2019-08-17.
* 301. 删除无效的括号
* <p>
* 删除最小数量的无效括号,使得输入的字符串有效,返回所有可能的结果。
* <p>
* 说明: 输入可能包含了除 ( 和 ) 以外的字符。
* <p>
* 示例 1:
* <p>
* 输入: "()())()"
* 输出: ["()()()", "(())()"]
* 示例 2:
* <p>
* 输入: "(a)())()"
* 输出: ["(a)()()", "(a())()"]
* 示例 3:
* <p>
* 输入: ")("
* 输出: [""]
* <p>
* <p>
* 来源:力扣(LeetCode)
* 链接:https://leetcode-cn.com/problems/remove-invalid-parentheses
* 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*/
public class _301_removeInvalidParentheses {
public static void main(String[] args) {
_301_removeInvalidParentheses removeInvalidParentheses = new _301_removeInvalidParentheses();
List<String> strings = removeInvalidParentheses.removeInvalidParentheses("(a)())()");
Util.printStringList(strings);
}
private Set<String> validExpressions = new HashSet<String>();
private void recurse(
String s,
int index,
int leftCount,
int rightCount,
int leftRem,
int rightRem,
StringBuilder expression) {
// If we reached the end of the string, just check if the resulting expression is
// valid or not and also if we have removed the total number of left and right
// parentheses that we should have removed.
if (index == s.length()) {
if (leftRem == 0 && rightRem == 0) {
this.validExpressions.add(expression.toString());
}
} else {
char character = s.charAt(index);
int length = expression.length();
// The discard case. Note that here we have our pruning condition.
// We don't recurse if the remaining count for that parenthesis is == 0.
if ((character == '(' && leftRem > 0) || (character == ')' && rightRem > 0)) {
this.recurse(
s,
index + 1,
leftCount,
rightCount,
leftRem - (character == '(' ? 1 : 0),
rightRem - (character == ')' ? 1 : 0),
expression);
}
expression.append(character);
// Simply recurse one step further if the current character is not a parenthesis.
if (character != '(' && character != ')') {
this.recurse(s, index + 1, leftCount, rightCount, leftRem, rightRem, expression);
} else if (character == '(') {
// Consider an opening bracket.
this.recurse(s, index + 1, leftCount + 1, rightCount, leftRem, rightRem, expression);
} else if (rightCount < leftCount) {
// Consider a closing bracket.
this.recurse(s, index + 1, leftCount, rightCount + 1, leftRem, rightRem, expression);
}
// Delete for backtracking.
expression.deleteCharAt(length);
}
}
public List<String> removeInvalidParentheses(String s) {
int left = 0, right = 0;
// First, we find out the number of misplaced left and right parentheses.
for (int i = 0; i < s.length(); i++) {
// Simply record the left one.
if (s.charAt(i) == '(') {
left++;
} else if (s.charAt(i) == ')') {
// If we don't have a matching left, then this is a misplaced right, record it.
right = left == 0 ? right + 1 : right;
// Decrement count of left parentheses because we have found a right
// which CAN be a matching one for a left.
left = left > 0 ? left - 1 : left;
}
}
this.recurse(s, 0, 0, 0, left, right, new StringBuilder());
return new ArrayList<String>(this.validExpressions);
}
}