leetcode_22括号匹配

1. 题意

给定整数n, 生成所有n个括号对的序列。
括号匹配

2. 题解

回溯法生成所有序列，再判断是否合法。

2.1 暴力

class Solution {
public:


    vector<string> generateParenthesis(int n) {
        
        vector<string> ans;
       string str;
       gen_all(str, 2 * n, ans);


        return ans;
    }
    
    bool isValid(string &str) {
        int sz = str.size();
        int l = 0;
        for (int i = 0; i < sz; ++i){
            if (l < 0)
                return false;
            
            if (str[i] == '(')
                ++l;
            else if (str[i] == ')')
                --l;
        }

        return l == 0;
    }


    void gen_all(string &str, int n, vector<string> &ans) {

        if (n == 0) {

            if (isValid(str)) {
                ans.push_back(str);
                cout << str <<　endl;
            }
            return ;
        }

        str += '(';
        gen_all(str, n - 1, ans);
        str.pop_back();


        str += ')';
        gen_all(str, n - 1, ans);
        str.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
54
55
56

2.2 暴力+减枝

我们可以记录左右括号的位置，当左括号数目多于n时退出，当右括号等于左括号数退出。

```cpp
class Solution {
public:


    vector<string> generateParenthesis(int n) {
        
        vector<string> ans;
        string str;
        gen_all(str, n, ans, 0, 0);


        return ans;
    }


    void gen_all(string &str, int n, vector<string> &ans, int l, int r) {

        if (str.size() == 2 * n) {
            ans.push_back(str);
            return ;
        }

        if ( l < n ) {
            str += '(';
            gen_all(str, n , ans, l + 1, r );
            str.pop_back();
        }

        if ( l > r) {
            str += ')';
            gen_all(str, n , ans, l, r + 1 );
            str.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

2.3 枚举左括号位置

官方给出的第三个解法，不是很明白为啥这么做。

大意就是，对于一个长度为n合法括号序列，它能表示为(a)b,a与b皆为合法序列。

这样就可以通过枚举括号序列a 和b 来求得合法序列。

首先明确合法序列的第一个字符一定为( ，所以官解在这里的意思我猜想是枚举与第一个左括号匹

配的右括号的位置来进行递归。

直接贴官解了。

class Solution {
    shared_ptr<vector<string>> cache[100] = {nullptr};
public:


    shared_ptr<vector<string> > gen(int n) {
        if ( cache[n] != nullptr)
            return cache[n];
        
        if ( n == 0) {
            cache[0] = shared_ptr<vector<string> > (new vector<string>{""});
        }
        else {
            auto res = shared_ptr<vector<string> >( new vector<string>);

            for (int i = 0; i != n; ++i) {
                auto lefts = gen(i);
                auto rights = gen(n - i - 1);

                for (const string &left: *lefts)
                    for ( const string &right: *rights)
                        res->push_back("(" + left + ")" + right );
            }
            cache[n] = res;
        }
        return cache[n];
    }

    vector<string> generateParenthesis(int n) {
        return *gen(n);
    }



};
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