问题描述
给定一个包含 (、) 和字母的字符串，要求去除字符串中的某些字符，使其满足括号匹配。要求找出所有删除字符数最小的字符串。题目链接：**点我**
样例输入输出
输入：s = “(a)())()”
输出：[“(a())()”,”(a)()()”]
输入：s = “)(“
输出：[“”]
问题解法
题目要求找出所有满足要求的字符串，所以只能用遍历搜索的方式，为了提高效率，在搜索过程中需要进行剪枝，比如已经搜索过的字符串就不要再进行搜索，又比如待搜索的字符串长度小于已经找到的满足要求的字符串长度就不用再进行搜索。另一个优化的地方就是判断字符串是否满足括号匹配的规则，不是使用栈，而是直接用数量进行判断。代码如下
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
| class Solution {
private int length = -1;
public List<String> removeInvalidParentheses(String s) {
Set<String> candidates = new HashSet<>();
Set<String> used = new HashSet<>();
search(s, candidates, used);
int maxLength = candidates.stream().mapToInt(String::length).max().getAsInt();
return candidates.stream().filter(item -> item.length() == maxLength).collect(Collectors.toList());
}
private void search(String str, Set<String> candidates, Set<String> used) {
if (str.length() < length || used.contains(str)) {
return;
}
boolean valid = isValid(str);
if (valid) {
if (str.length() >= length) {
candidates.add(str);
length = str.length();
used.add(str);
}
return;
}
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(' || str.charAt(i) == ')') {
String temp = str.substring(0, i) + str.substring(i + 1);
search(temp, candidates, used);
used.add(temp);
}
}
}
private boolean isValid(String str) {
int leftCount = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
leftCount++;
continue;
}
if (str.charAt(i) == ')') {
leftCount--;
if (leftCount < 0) {
return false;
}
}
}
return leftCount == 0;
}
}
|