Parens: Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n pairs of parentheses.
1
2
3
|
EXAMPLE
Input: 3
Output: ((())), (()()), (())(), ()(()), ()()()
|
Hints: #138, #174, #187, #209, #243, #265, #295
解法1
这个问题的难点在于如果你把所有的可插入点都去插一下，那么会得到重复的结果，比如插入点有这么几个：
()的里面()的左边()点右边
即使我们去掉左边这个插入点，那么依然会存在重复，比如：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
下面用()代表之前得到的结果，[]代表本步骤新插入的结果：
f(1) = ()
f(2) = 在 f(1) 的插入点插入
= ()[]
([])
f(3) = 在 f(2) 的插入点插入
= ([])() case 1 插里面
()[]() case 2 插右边
()([]) case 3 插里面
()()[] case 4 插右边
(([])) case 5 插里面
(()[]) case 6 插右边
(())[] case 7 插右边
case 1和case 7重复
case 2和case 4重复
|
用什么办法做插入才能不产生重复？如果用HashSet来排重的话太复杂了。
解法2(正确)
把(记为L，把)记为R，这个问题是否可以理解为给定2 * n个空位，让你在里面填上L和R。
要求一：结果的L和R的数量相等
如果我们从第一个空格开始填，那么应该填什么？基本上来说你填L肯定是安全的（只要没超数量就行），那么什么时候填R呢？当count(R) < count(L)的时候可以。如果你从左到右读一个合法的结果，在读的时候给L和R计数，那么你会发现R的计数永远不会超过L。所以总结一下：
- 最终结果count(L) == count(R)
- count(L) == n
- 当count(R) < count(L) 的时候可以填写R
- 当count(L) < n的时候可以填写L
- 当count(R) == count(L) == 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
|
public List<String> parens(int n) {
List<String> result = new ArrayList<>();
parens(new StringBuilder(), n, n, result);
return result;
}
// lCount: ( 剩余的数量，这里和上面有点差别，上面说的是迄今为止用了多少个L，这里是还剩多少个 ( 没用。
// rCount: ) 剩余的数量
public void parens(StringBuilder sb, int lCount, int rCount, List<String> result) {
if (lCount == 0 && rCount == 0) {
result.add(sb.toString());
return;
}
if (lCount > 0) {
sb.append('(');
parens(sb, lCount - 1, rCount, result);
sb.deleteAt(sb.length() - 1);
}
if (rCount > 0 && rCount > lCount) {
sb.append(')');
parens(sb, lCount, rCount - 1, result);
sb.deleteAt(sb.length() - 1);
}
}
|
评论