forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathGenerate Parentheses.java
More file actions
134 lines (119 loc) · 3.01 KB
/
Generate Parentheses.java
File metadata and controls
134 lines (119 loc) · 3.01 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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
递归。
看thought.取或者不取(, )
```
/*
Generate Parentheses
Given n pairs of parentheses,
write a function to generate all combinations of well-formed parentheses.
Example
Given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
Tags Expand
String Backtracking Recursion Zenefits Google
*/
/*
Thoughts:
//http://fisherlei.blogspot.com/2012/12/leetcode-generate-parentheses.html
Either put ( or )
can only put ( when # of ( < n
can only put ) when # of ) < # of (
If # of single '(' > 0, then we can put ')'
If n > 0, we can split: 1. close it with ')'; or 2. add '('
when n-- becomese = 0 and #p = 0, rst.add
*/
public class Solution {
/**
* @param n n pairs
* @return All combinations of well-formed parentheses
*/
ArrayList<String> rst = new ArrayList<String>();
public ArrayList<String> generateParenthesis(int n) {
if (n <= 0) {
return rst;
}
ArrayList<String> list = new ArrayList<String>();
helper(list, 0, 0, n);
return rst;
}
public void helper(ArrayList<String> list, int left, int right, int n) {
if (left == n && right == n) {
StringBuffer sb = new StringBuffer();
for (String s : list) {
sb.append(s);
}
rst.add(sb.toString());
return;
}
if (left < n) {
list.add("(");
helper(list, left + 1, right, n);
list.remove(list.size() - 1);
}
if (right < left) {
list.add(")");
helper(list, left, right + 1, n);
list.remove(list.size() - 1);
}
}
}
/*
//
1st attempt, timeout.
Thoughts:
n = 0, null
n = 1, trivial: ()
Do i-- from n. For each i >= 2
it can choose: close a paren
open another paren
front = (
end = )
helper(front, end, int n)
if (n == 1) {
front + "()" + end
rst.add // check duplicate
}
*/
public class Solution {
/**
* @param n n pairs
* @return All combinations of well-formed parentheses
*/
public ArrayList<String> rst = new ArrayList<String>();
public ArrayList<String> generateParenthesis(int n) {
if (n <= 0) {
return rst;
} else if (n == 1){
rst.add("()");
return rst;
}
helper("", "", n);
Collections.sort(rst);
return rst;
}
//3
public void helper(String front, String end, int n) {
if (n == 1) {
String rt = front + "()" + end;
if (!rst.contains(rt)){
rst.add(rt);
}
return;
}
n--;
helper(front + "(", ")" + end, n);
helper(front + "()", end, n);
helper(front, "()" + end, n);
helper(front + end + "(", ")", n);
helper(front + end, "()", n);
helper(front + end + "()", "", n);
helper("(", ")" + front + end, n);
helper("()", front + end, n);
helper("","()" + front + end, n);
helper("(",front+end+")",n);
helper("(" + front+end,")",n);
helper("(" + front, end + ")",n);
helper("("+front+end+")", "", n);
helper("", "("+front+end+")", n);
}
}
```