Luobuyu's Blog

0%

301.删除无效的括号

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 1.5k 阅读时长 ≈ 1 分钟
枚举尝试删除每一个，注意如果出现重复的可以剪枝。

301.删除无效的括号

题目描述：

给出一个由若干括号和字母组成的字符串s，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果，答案可以按任意顺序返回。s由小写字母和括号组成。

数据范围：
$ 1\le s.length\le 25 $

题解：

首先计算出左括号和右括号各有多少个需要删除记为 $ l,r $ 。然后将每一个括号都尝试删除，每个括号选择删或者不删。

剪枝：

  • 如果剩余字符的数量不足以删除 $ 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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    vector<string> ans;
    string tmp;
    void dfs(int step, int l, int r, int n, string &s)
    {
        if (l == 0 && r == 0)
        {
            if (check(s))
            {
                tmp = "";
                for (int i = 0; i < s.length(); ++i)
                {
                    if (s[i] != '.')
                        tmp.push_back(s[i]);
                }
                ans.emplace_back(tmp);
            }
            return;
        }
        if (l + r > n - step)
            return;
        if (step > 0 && s[step] == s[step - 1])
            dfs(step + 1, l, r, n, s);
        else if (l > 0 && s[step] == '(')
        {
            s[step] = '.';
            dfs(step + 1, l - 1, r, n, s);
            s[step] = '(';
            dfs(step + 1, l, r, n, s);
        }
        else if (r > 0 && s[step] == ')')
        {
            s[step] = '.';
            dfs(step + 1, l, r - 1, n, s);
            s[step] = ')';
            dfs(step + 1, l, r, n, s);
        }
        else if (s[step])
            dfs(step + 1, l, r, n, s);
    }
    bool check(string& s)
    {
        int tmp = 0;
        for (int i = 0; i < s.length(); ++i)
        {
            if (s[i] == '(')
                tmp++;
            else if (s[i] == ')')
            {
                tmp--;
                if (tmp < 0)
                    return false;
            }
        }
        return tmp == 0;
    }
    vector<string> removeInvalidParentheses(string s)
    {
        int l = 0, r = 0;
        for (int i = 0; i < s.length(); ++i)
        {
            if (s[i] == '(')
                l++;
            else if (s[i] == ')')
                if (l == 0)
                    r++;
                else
                    l--;
        }
        string cur;
        dfs(0, l, r, s.length(), s);
        return ans;
    }
};