LeetCode301 删除无效的括号

链接: https://leetcode-cn.com/problems/remove-invalid-parentheses/

题面

给你一个由若干括号和字母组成的字符串 s ,删除最小数量的无效括号,使得输入的字符串有效。
返回所有可能的结果。

解法

由于数据量不大,字符串最大长度只有25
所以考虑搜索解决
对于每个字符串,要判断它是否是合法的括号字符串,需要满足

  1. 左括号的数量等于右括号的数量
  2. 从左往右遍历的过程中,不能出现右括号多于左括号的情况
    进行DFS,对于每一位取或者不取,遇到左括号score加1,遇到右括号score减1
    如果遇到score小于说明当前子串不合法
    将所有的合法的结果塞入一个set进行去重 得到最后的结果
    这样属于暴力解法,你可以打败5%的用户

考虑剪枝

由于左括号和右括号的数目都是确定的
所以可以进行预处理,处理出最多的左括号和右括号的数量作为max_score
如果在过程中发现分数超过这个max_score,则说明必然不存在足够多的右括号数使得score变为0
通过这一方式进行剪枝
代码如下

进一步剪枝

考虑到其实在从左往右检索的过程中
通过计算score其实已经可以得出最长的合法字符串长度
也可以知道通过预处理
计算出需要删去的左括号数量和右括号数量
通过在递归检索的过程中判断这一条件 来进行进一步的剪枝优化

代码

剪枝1

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
class Solution {
public:
int max_score, max_len;
set<string> ans;
void dfs(int loc, int score, string t, string& s) {
if (score < 0 || score > max_score) return;
if (loc >= s.size()) {
if (score == 0) {
if (max_len < t.size()) {
if (ans.size()) {
ans.clear();
}
ans.insert(t);
max_len = t.size();
}
else if (max_len == t.size()) {
ans.insert(t);
}
}
return;
}
if (s[loc] == '(') {
dfs(loc + 1, score, t, s);
dfs(loc + 1, score + 1, t + "(", s);
}
else if (s[loc] == ')') {
dfs(loc + 1, score, t, s);
dfs(loc + 1, score - 1, t + ")", s);
}
else {
dfs(loc + 1, score, t + s[loc], s);
}
}
vector<string> removeInvalidParentheses(string s) {
int l = 0, r = 0;
for (char c: s) {
if (c == '(') l++;
else if (c == ')') r++;
}
max_score = min(l, r);
dfs(0, 0, "", s);
vector<string> ret;
for (auto i: ans) {
ret.push_back(i);
}
return ret;
}
};

剪枝2

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
class Solution {
public:
int max_score, max_len;
set<string> ans;
void dfs(int loc, int score, string t, string& s, int l ,int r) {
if (score < 0 || score > max_score || l < 0 || r < 0) return;
if (loc == s.size()) {
if (score == 0 && t.size() == max_len) {
ans.insert(t);
}
return;
}
if (s[loc] == '(') {
dfs(loc + 1, score, t, s, l - 1, r);
dfs(loc + 1, score + 1, t + "(", s, l, r);
}
else if (s[loc] == ')') {
dfs(loc + 1, score, t, s, l, r - 1);
dfs(loc + 1, score - 1, t + ")", s, l, r);
}
else {
dfs(loc + 1, score, t + s[loc], s, l, r);
}
}
vector<string> removeInvalidParentheses(string s) {
int l = 0, r = 0;
for (char c: s) {
if (c == '(') l++;
else if (c == ')') r++;
}
max_score = min(l, r);
l = 0, r = 0;
for (char c: s) {
if (c == '(') l++;
else if (c == ')') {
if (l > 0) l--;
else r++;
}
}
max_len = s.size() - l - r;
dfs(0, 0, "", s, l, r);
vector<string> ret;
for (auto i: ans) {
ret.push_back(i);
}
return ret;
}
};