LeetCode 22. Generate Parentheses

假设有n对括号,让你生成所有的有效的括号序列。

分析

官方给出了三种方法,一是暴力法,生成所有可能的序列,然后再判断该序列是否有效;二是回溯法,即在生成括号的过程中就进行判断,主要是根据当前左右括号的数量。

第三种方法比较类似分治?因为第一个位置一定要是个(,那么和该括号匹配的)就需要在一个奇数位置(从0开始),这样这对括号之间才能空出偶数个空,才能放置有效的括号序列,类似这样:

1
(..A..)..B..

若与第一个(匹配的)的坐标设为2*i+1(0<=i<n),那么片段A就是包含i对括号的有效序列,片段B就是包含n-i-1对括号的有效序列,假设n对括号的有效序列数设为f(n),那么就有下式:

1
f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-1)*f(0)

实现

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
public class Beauty0403 {

static int n = 2;
static ArrayList<String>[] caches = new ArrayList[2*n];
public static void main(String[] args) {
caches[0] = new ArrayList<>();
caches[0].add("");
List<String> generate = generate(n);
System.out.println(generate);
}

public static List<String> generate(int n) {
if (caches[n] != null) {
return caches[n];
}
caches[n] = new ArrayList<>();
ArrayList<String> ans = new ArrayList<>();
for (int i = 0; i <= n-1; i ++) {
for (String sf : generate(i)) {
for (String ss : generate(n-i-1)) {
ans.add("(" + sf + ")" + ss);
}
}
}
caches[n] = ans;
return ans;
}
}

补充

上述表达式和Catalan Number的定义类似,而且还有很多问题都和Catalan Number相关,比如编程之美的4.3,及其扩展问题,还有wiki上举的一些例子。

有些题目很容易理解,取值范围和Catalan Number一致时,可以直接套上边的模板,但是有个多边形划分为三角形问题,就不太一样。