LeetCode301 删除无效的括号

发表于 | 分类于 |
字数统计: 824 | 阅读时长 ≈ 3

链接： 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;
    }
};