文章目錄

请写一个程序,输入一个正整数的值,然后列出所有有n个做括号与n个右括号正确地组成的字符串;当然,正确的左、右括号一定个数一样多。

说明:
所谓由括号正确地组成的字符串,指的是如果有一个左括号,那么在它的右边就一定有一个与它相匹配的右括号。(())、()(),就是仅有的两个由两个左括号和两个右括号正确地组成的字符串;((()))、(()())、(())()、()(())、()()()是仅有的5个由3个左括号和3个右括号正确地组成的字符串。

如何产生这样的字符串呢?下面就是一个有用的想法:如果在产生的过程中已经产生了若干左、右括号,为了要把产生的行为完成,还欠R个左括号、L个右括号,那么有没有办法找出产生下一个括号时L与R的关系呢?记住,递归是一个不容忽视的利器。
解法:
假设还有left个左括号和right个右括号等待匹配,根据left与right的大小可以分三种情况
1.当 left == right 时,此时只能继续放左括号
2.当 left < right时,可以有两个选择, 继续放一个左括号或者继续放一个有括号。
放左括号时需要判断left是否大于0,只有left大于0时,才能继续放左括号。
放右括号时则不需要判断。
3.当left > right时,此时没有意义。

写成Java程序如下:

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
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class GenerateParenthesis {
public static List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<String>();
generateParenthesis(n, n , n, "", result);
return result;
}
private static void generateParenthesis(int left, int right, int n,
String s, List<String> result) {

if (s.length() == n * 2) {
result.add(s);
} else {
if (left == right) {
generateParenthesis(left - 1, right, n , s + "(", result);
} else if (left < right) {
if (left > 0) {
generateParenthesis(left - 1, right, n , s + "(", result);
}
generateParenthesis(left, right - 1, n, s + ")", result);
}
}
}
public static void main(String[] args) {
List<String> result = generateParenthesis(3);
for (String s: result) {
System.out.println(s);
}
}
}

还可以对程序进行优化,因为递归过程会产生许多字符串,可以用数组来解决这个问题。修改程序如下:

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
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class GenerateParenthesis {
public static List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<String>();
char[] str = new char[n * 2];
generateParenthesis(n, n , str, 0, result);
return result;
}
private static void generateParenthesis(int left, int right, char[] str,
int length, List<String> result) {

if (length == str.length) {
result.add(String.valueOf(str));
} else {
if (left == right) {
str[length] = '(';
generateParenthesis(left - 1, right, str, length + 1, result);
} else if (left < right) {
if (left > 0) {
str[length] = '(';
generateParenthesis(left - 1, right, str, length + 1, result);
}
str[length] = ')';
generateParenthesis(left, right - 1, str, length + 1, result);
}
}
}
public static void main(String[] args) {
List<String> result = generateParenthesis(3);
for (String s: result) {
System.out.println(s);
}
}
}

文章目錄