-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathGenerateParenthesis.java
More file actions
108 lines (94 loc) · 2.97 KB
/
Copy pathGenerateParenthesis.java
File metadata and controls
108 lines (94 loc) · 2.97 KB
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
package com.gankki.demo.algorithm.leetcode.generateParenthesis22;
import javax.xml.stream.events.DTD;
import java.util.ArrayList;
import java.util.List;
/**
* 生成括号
*
* @author liuhao
* @date 2020/8/30
*/
public class GenerateParenthesis {
public static void main(String[] args) {
List<String> result = generateParenthesis2(2);
for (String s : result) {
System.out.println(s);
}
}
/**
* 2020/8/30 18:29 O(n^2) O(n) 暴力解法，先统计出所有可能性，然后再过滤有效的
* 一直在一个数组上操作，但是递归栈占用了内存空间，因此，空间复杂度为 O(n)
*/
public List<String> generateParenthesis1(int n) {
List<String> result = new ArrayList<>();
generateAll(new char[n * 2], 0, result);
return result;
}
private void generateAll(char[] chars, int pos, List<String> result) {
if (chars.length == pos) {
if (valid(chars)) {
result.add(new String(chars));
}
} else {
chars[pos] = '(';
generateAll(chars, pos + 1, result);
chars[pos] = ')';
generateAll(chars, pos + 1, result);
}
}
private boolean valid(char[] chars) {
int temp = 0;
for (char c : chars) {
if (c == '(') {
++temp;
} else {
--temp;
}
if (temp < 0) {
return false;
}
}
return temp == 0;
}
/**
* 2020/8/30 18:45 回溯法，用完的括号删除，重新利用字符串 O(n) O(1)
*/
public static List<String> generateParenthesis2(int n) {
List<String> result = new ArrayList<>();
generateAll2(new StringBuilder(), 0, 0, result, n);
return result;
}
private static void generateAll2(StringBuilder sb, int left, int right, List<String> result, int max) {
if (sb.length() == max * 2) {
result.add(sb.toString());
return;
}
if (left < max) {
sb.append("(");
generateAll2(sb, left + 1, right, result, max);
sb.deleteCharAt(sb.length() - 1);
}
if (left > right) {
sb.append(")");
generateAll2(sb, left, right + 1, result, max);
sb.deleteCharAt(sb.length() - 1);
}
}
public static List<String> generateParenthesis3(int n) {
List<String> result = new ArrayList<>();
generateAll3(0, 0, n, "", result);
return result;
}
private static void generateAll3(int left, int right, int n, String str, List<String> result) {
if (left == n && right == n) {
result.add(str);
return;
}
if (left < n) {
generateAll3(left + 1, right, n, str + "(", result);
}
if (left > right) {
generateAll3(left, right + 1, n, str + ")", result);
}
}
}