Code & Fun

打卡,第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
2
3
4
5
6
7
8
9
10
11
12
13
vector<string> generateParenthesis1(int n) {
if (n == 1) return {"()"};
set<string> ret;

vector<string> r = generateParenthesis(n-1);
for(auto s:r){
ret.insert(s+"()");
ret.insert("()" + s);
ret.insert("(" + s + ")");
}

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

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

故我们可以做以下改进,得到正确答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<string> generateParenthesis1(int n) {
if (n == 1) return {"()"};
set<string> ret;

vector<string> r = generateParenthesis(n-1);
for(auto s:r){
ret.insert(s+"()");
ret.insert("()" + s);
ret.insert("(" + s + ")");
}

for(int i = n/2;i > 1;i--) {
vector<string> r1 = generateParenthesis(n - i);
vector<string> r2 = generateParenthesis(i);
for(auto s1:r1)
for(auto s2:r2) {
ret.insert(s1+s2);
ret.insert(s2+s1);
}
}

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

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

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
vector<string> generateParenthesis(int n) {
vector<vector<string> > par{
{""}
};

for(int i = 1;i <= n;i++) {
set<string> now;
for(auto s:par[i-1]) {
now.insert(s + "()");
now.insert("()" + s);
now.insert("(" + s + ")");
}
int l = 1;
int r = i - l;
while(r >= l) {
//cout << l << " " << r << endl;
for(auto s1:par[l])
for(auto s2:par[r]){
//cout << s1 << " " << s2 << endl;
now.insert(s1+s2);
now.insert(s2+s1);
}
l++;
r--;
}
par.push_back({now.begin(),now.end()});
}
return par[n];
}

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

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
vector<string> result;
vector<string> generateParenthesis(int n) {
helper("", n, 0);
return result;
}

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

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

void helper(string s, int leftpare_need, int moreleft)
{
if(leftpare_need == 0 && moreleft == 0)
{
result.push_back(s);
return;
}
if(leftpare_need > 0)
helper(s + "(", leftpare_need - 1, moreleft+1);
if(moreleft > 0)
helper(s + ")", leftpare_need, moreleft - 1);
}

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


本文首发于Code & Fun