Code & Func

打卡，第15天

今天做了一道比较好玩的题，之前有做个一个括号匹配的题目，今天的题目刚好反过来，不是验证括号是否正确，而是生成正确括号——Generate Parentheses.

题目描述：

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

1
[
2
  "((()))",
3
  "(()())",
4
  "(())()",
5
  "()(())",
6
  "()()()"
7
]

再看看n = 2时：

1
[
2
    "(())",
3
    "()()",
4
]

我们观察上面的例子，可以发现n=3,其实是由n=2加上一个()组合起来的，可以分成三种情况：

在前面加上(),
在后面加上(),
在前面加上(后面加上)

我们大概可以写出这样的代码：

1
vector<string> generateParenthesis1(int n) {
2
    if (n == 1) return {"()"};
3
    set<string> ret;
4

5
    vector<string> r = generateParenthesis(n-1);
6
    for(auto s:r){
7
        ret.insert(s+"()");
8
        ret.insert("()" + s);
9
        ret.insert("(" + s + ")");
10
    }
11

12
    return {ret.begin(),ret.end()};
13
}

这样在n <= 3时是ok的，但是如果n = 4还有一种可能，就是(())(()),这时由两个n=2的括号组合而成的，以及n = 5时，可以由n = 3和n = 2组合而成，也可以由n = 1和n = 4组合而成。

故我们可以做以下改进，得到正确答案：

1
vector<string> generateParenthesis1(int n) {
2
    if (n == 1) return {"()"};
3
    set<string> ret;
4

5
    vector<string> r = generateParenthesis(n-1);
6
    for(auto s:r){
7
        ret.insert(s+"()");
8
        ret.insert("()" + s);
9
        ret.insert("(" + s + ")");
10
    }
11

12
    for(int i = n/2;i > 1;i--) {
13
        vector<string> r1 = generateParenthesis(n - i);
14
        vector<string> r2 = generateParenthesis(i);
15
        for(auto s1:r1)
8 collapsed lines
16
            for(auto s2:r2) {
17
                ret.insert(s1+s2);
18
                ret.insert(s2+s1);
19
            }
20
    }
21

22
    return {ret.begin(),ret.end()};
23
}

可以发现，这里出现了很多次重复计算，可以用动态规划去做：

1
vector<string> generateParenthesis(int n) {
2
    vector<vector<string> > par{
3
        {""}
4
    };
5

6
    for(int i = 1;i <= n;i++) {
7
        set<string> now;
8
        for(auto s:par[i-1]) {
9
            now.insert(s + "()");
10
            now.insert("()" + s);
11
            now.insert("(" + s + ")");
12
        }
13
        int l = 1;
14
        int r = i - l;
15
        while(r >= l) {
14 collapsed lines
16
            //cout << l << " " << r << endl;
17
            for(auto s1:par[l])
18
                for(auto s2:par[r]){
19
                    //cout << s1 << " " << s2 << endl;
20
                    now.insert(s1+s2);
21
                    now.insert(s2+s1);
22
                }
23
            l++;
24
            r--;
25
        }
26
        par.push_back({now.begin(),now.end()});
27
    }
28
    return par[n];
29
}

然后是在discuss中看到的另一种思路：

1
vector<string> result;
2
vector<string> generateParenthesis(int n) {
3
    helper("", n, 0);
4
    return result;
5
}
6

7
/*  this hepler function insert result strings to "vector<string> result"
8
    When number of '(' less than "n", can append '(';
9
    When number of '(' is more than number of ')', can append ')';
10

11
    string s : current string;
12
    int leftpare_need : number of '(' that have not put into "string s";
13
    int moreleft : number of '(' minus number of ')' in the "string s";
14
*/
15

12 collapsed lines
16
void helper(string s, int leftpare_need, int moreleft)
17
{
18
    if(leftpare_need == 0 && moreleft == 0)
19
    {
20
        result.push_back(s);
21
        return;
22
    }
23
    if(leftpare_need > 0)
24
        helper(s + "(", leftpare_need - 1, moreleft+1);
25
    if(moreleft > 0)
26
        helper(s + ")", leftpare_need, moreleft - 1);
27
}

这个的想法是，不断的生成左括号，有左括号，后面就一定会生成一个右括号。