题目解析

删除不合法的括号,比如下面的样例

1
2
输入: "(a)())()"
输出: ["(a)()()", "(a())()"]

方法一 慢

这道题好像没什么好方法,直接用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
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
helper(s, "", 0, 0, 0);
vector<string> temp;
int len = INT_MIN;
for (string r: result) {
len = max(static_cast<int>(r.size()), len);
}
for (string r: result) {
if (r.size() == len) {
temp.push_back(r);
}
}
return temp;
}
void helper(string &s, string one, int index, int left, int right) {
if (index == s.size()) {
if (left == right && valid(one)) {
result.insert(one);
}
return;
}
if (left < right) return;
if (s[index] != '(' && s[index] != ')') {
helper(s, one+s[index], index+1, left, right);
return;
}
int l = 0, r = 0;
if (s[index] == '(') l=1;
if (s[index] == ')') r=1;
helper(s, one + s[index], index+1, left+l, right+r);
helper(s, one, index+1, left, right);
}
bool valid(string & p) {
int count = 0;
for (char c : p) {
if (c == '(') count++;
if (c == ')') count--;
if (count < 0) return false;
}
return true;
}
int min_len = INT_MAX;
unordered_set<string> result;
};

方法二 快

可以在递归前计算出需要删除的左右括号数量,每次删除到指定括号的时候,减少对应的l,r

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 {
public:
vector<string> removeInvalidParentheses(string s) {
int l = 0, r = 0;
// ")()" 需要删除右括号1个
// "())(()" 需要删除左括号1个,右括号1个
for (char c : s) { // 需要删除的左右括号数
if (c == '(') l++;
else if (c == ')') {
if (l == 0) r++;
else l--;
}
}
helper(s, "", 0, l, r);
vector<string> temp;
int len = INT_MIN;
for (string s: result) {
len = max(static_cast<int>(s.size()), len);
}
for (string s: result) {
if (s.size() == len) {
temp.push_back(s);
}
}
return temp;
}
void helper(string &s, string one, int index, int left, int right) {
if (index == s.size()) {
if (left == 0 && left == right && valid(one)) {
result.insert(one);
}
return;
}
if (left < 0 || right < 0) return;
if (s[index] != '(' && s[index] != ')') {
helper(s, one+s[index], index+1, left, right);
return;
}
int l = 0, r = 0;
if (s[index] == '(') l=1;
if (s[index] == ')') r=1;
helper(s, one, index+1, left-l, right-r);
helper(s, one+s[index], index+1, left, right);
}
bool valid(string & p) {
int count = 0;
for (char c : p) {
if (c == '(') count++;
if (c == ')') count--;
if (count < 0) return false;
}
return true;
}
int min_len = INT_MAX;
unordered_set<string> result;
};