Mind palace

some thoughts

0%

22. Generate Parentheses

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

backtracking O(2n) time
思路是只要左括号比右括号多就是合法的！！！

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def gen(s, l, r):
            if l < 0 or r < 0 or l > r: return
            if not l and not r:
                res.append(s) # 注意这里不能用res += s因为s是Iterable会逐个追加，想整体追加要用append
                return
            gen(s + '(', l - 1, r) # 这里底层内存需要进行字符串复制，但是没办法，Python字符串literal不能修改，也不提供StringBuilder
            gen(s + ')', l, r - 1)
        gen('', n, n)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        string s;
        dfs(s, n, n);
        return res;
    }

    void dfs(string &s, int nl, int nr) {
        if (nl < 0 || nr < 0 || nl > nr) return;
        if (nl == 0 && nr == 0) {
            res.push_back(s);
            return;
        }
        dfs(s += '(', nl - 1, nr);
        s.pop_back();
        dfs(s += ')', nl, nr - 1);
        s.pop_back();
    }

    vector<string> res;
};
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
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        nl = nr = n;
        string s;
        dfs(s);
        return res;
    }

    void dfs(string &s) {
        if (nl == 0 && nr == 0) {
            res.push_back(s);
            return;
        }
        if (nl == 0) {
            --nr;
            dfs(s += ')');
            ++nr;
            s.pop_back();
        } else if (nl == nr) {
            --nl;
            dfs(s += '(');
            ++nl;
            s.pop_back();
        } else {
            --nl;
            dfs(s += '(');
            ++nl;
            s.pop_back();
            --nr;
            dfs(s += ')');
            ++nr;
            s.pop_back();
        }
    }

    int nl, nr;
    vector<string> res;
};

如果需要轴对称

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
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        string s;
        this->n = n;
        dfs(s, n, n);
        return res;
    }

    void dfs(string &s, int nl, int nr) {
        if (nl < 0 || nr < 0 || nl > nr) return;
        if (nl + nr == n) {
            res.push_back(s);
            for (int i = n - 1; i >= 0; --i) {
                if (s[i] == '(') {
                    res.back() += ')';
                } else {
                    res.back() += '(';
                }
            }
            return;
        }
        dfs(s += '(', nl - 1, nr);
        s.pop_back();
        dfs(s += ')', nl, nr - 1);
        s.pop_back();
    }

    int n;
    vector<string> res;
};