Cinte's Leetcode Record
0%

301. 删除无效的括号

Posted on Edited on In Disqus:
Symbols count in article: 3.2k Reading time ≈ 3 mins.

301. 删除无效的括号

BackTrack
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
80
81
82
83
84
85
86
87
88
89
90
class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        // 记录左右括号数，当碰到右括号时，若左括号数不为0，那么左括号数减一，表示这是一对合法括号，
        // 若左括号数为0，那么右括号数加一，这是一个需要删除的括号
        // 若遇到左括号，那么由于合法左括号不会出现在右括号之后，因此只需要左括号数加一即可
        // 剩下的左括号数和右括号数就是应当删除的括号数
        for(auto& ch : s)
        {
            if(ch == '(')
                ++leftCount;
            else if(ch == ')')
            {
                if(leftCount == 0)
                    ++rightCount;
                else
                    --leftCount;
            }
        }
        // 开始回溯
        string tmp = "";
        helper(s, 0, tmp, 0, 0);
        return ret;
    }
private:
    vector<string> ret;
    unordered_set<string> set;
    // 记录无效的左右括号数
    int leftCount = 0;
    int rightCount = 0;
private:
    void helper(string& s, int index, string& tmp, int curLeft, int curRight)
    {
        if(index == s.size())
        {
            // 当左括号和右括号全都删掉后，由于回溯过程中保证左括号小于右括号，所以此时必定为合法的。然后使用set去重
            if(set.emplace(tmp).second && leftCount == 0 && rightCount == 0) // 这种似乎会超时，需要用下面那种的写法
                ret.push_back(tmp);
            return;
        }

        if(s[index] == '(')
        {
            // 若左括号没有删除完
            if(leftCount != 0)
            {
                // 删除这个左括号，开始回溯
                --leftCount;
                helper(s, index + 1, tmp, curLeft, curRight);
                ++leftCount;
            }
            // 保留这个左括号，开始回溯
            tmp += '(';
            ++curLeft; // 当前的左括号数+1
            helper(s, index + 1, tmp, curLeft, curRight);
            --curLeft;
            tmp.pop_back();
        }else if(s[index] == ')')
        {
            // 只有目前遇到的左括号数>右括号数时，才可以选择删除这个右括号或者保留
            if(curLeft > curRight)
            {
                // 与左括号类似
                if(rightCount != 0)
                {
                    --rightCount;
                    helper(s, index + 1, tmp, curLeft, curRight);
                    ++rightCount;
                }
                tmp += ')';
                ++curRight;
                helper(s, index + 1, tmp, curLeft, curRight);
                --curRight;
                tmp.pop_back();
            // 当左括号数==右括号数时，只能抛弃这个右括号，不能保留，否则就是无效状态了
            }else if(curLeft == curRight)
            {
                --rightCount;
                helper(s, index + 1, tmp, curLeft, curRight);
                ++rightCount;
            }
        }else
        {
            // 碰到字母，就保留
            tmp += s[index];
            helper(s, index + 1, tmp, curLeft, curRight);
            tmp.pop_back();
        }
    }
};

精简优化,思路同上

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
class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        for(auto& ch : s)
        {
            if(ch == ')')
            {
                if(leftCount == 0)
                    ++rightCount;
                else
                    --leftCount;
            }else if(ch == '(')
                ++leftCount;
        }
        string tmp;
        helper(s, 0, s.size(), 0, 0, tmp);
        vector<string> ret(set.begin(), set.end());
        return ret;
    }
private:
    unordered_set<string> set;
    int leftCount = 0;
    int rightCount = 0;
    void helper(string& s, int index, int sz, int curLeft, int curRight, string& tmp)
    {
        if(index == sz)
        {
            if(leftCount == 0 && rightCount == 0)
                set.insert(tmp);
            return;
        }
        auto ch = s[index];
        if(ch == '(' && leftCount)
        {
            --leftCount;
            helper(s, index + 1, sz, curLeft, curRight, tmp);
            ++leftCount;
        }else if(ch == ')' && rightCount)
        {
            --rightCount;
            helper(s, index + 1, sz, curLeft, curRight, tmp);
            ++rightCount;
        }
        tmp += ch;
        if(ch != ')' && ch != '(')
            helper(s, index + 1, sz, curLeft, curRight, tmp);
        else if(ch == ')' && curLeft > curRight)
            helper(s, index + 1, sz, curLeft, curRight + 1, tmp);
        else if(ch == '(')
            helper(s, index + 1, sz, curLeft + 1, curRight, tmp);
        tmp.pop_back();
    }
};
BFS

对于一串，每层把每个括号都删掉一次试试看，然后进入下一层，每层删掉的括号是一致的，当一层碰到有效后，把这一层所有有效的加入然后返回。

。。。。不想写（抄