Skip to content

Commit 2ad2437

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0022. Generate Parentheses
1 parent 41fa01b commit 2ad2437

File tree

6 files changed

+206
-19
lines changed

6 files changed

+206
-19
lines changed

‎solution/0000-0099/0022.Generate Parentheses/README.md

Lines changed: 79 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -44,15 +44,93 @@
4444
<!-- 这里可写当前语言的特殊实现逻辑 -->
4545

4646
```python
47-
47+
class Solution:
48+
def generateParenthesis(self, n: int) -> List[str]:
49+
def dfs(ans, l, r, n):
50+
if len(ans) == (n << 1):
51+
self.res.append(ans)
52+
return
53+
if l < n:
54+
dfs(ans + '(', l + 1, r, n)
55+
if r < l:
56+
dfs(ans + ')', l, r + 1, n)
57+
58+
self.res = []
59+
dfs('', 0, 0, n)
60+
return self.res
4861
```
4962

5063
### **Java**
5164

5265
<!-- 这里可写当前语言的特殊实现逻辑 -->
5366

5467
```java
68+
class Solution {
69+
public List<String> generateParenthesis(int n) {
70+
List<String> res = new ArrayList<>();
71+
dfs(res, "", 0, 0, n);
72+
return res;
73+
}
74+
75+
private void dfs(List<String> res, String ans, int l, int r, int n) {
76+
if (ans.length() == (n << 1)) {
77+
res.add(ans);
78+
return;
79+
}
80+
if (l < n) {
81+
dfs(res, ans + "(", l + 1, r, n);
82+
}
83+
if (r < l) {
84+
dfs(res, ans + ")", l, r + 1, n);
85+
}
86+
}
87+
}
88+
```
89+
90+
### **C++**
91+
92+
```cpp
93+
class Solution {
94+
public:
95+
vector<string> generateParenthesis(int n) {
96+
vector<string> res;
97+
dfs(res, "", 0, 0, n);
98+
return res;
99+
}
100+
101+
private:
102+
void dfs(vector<string>& res, string ans, int l, int r, int n) {
103+
if (ans.size() == (n << 1)) {
104+
res.push_back(ans);
105+
return;
106+
}
107+
if (l < n) dfs(res, ans + "(", l + 1, r, n);
108+
if (r < l) dfs(res, ans + ")", l, r + 1, n);
109+
}
110+
};
111+
```
55112
113+
### **Go**
114+
115+
```go
116+
func generateParenthesis(n int) []string {
117+
res := new([]string)
118+
dfs(res, "", 0, 0, n)
119+
return *res
120+
}
121+
122+
func dfs(res *[]string, ans string, l, r, n int) {
123+
if len(ans) == (n << 1) {
124+
*res = append(*res, ans)
125+
return
126+
}
127+
if l < n {
128+
dfs(res, ans+"(", l+1, r, n)
129+
}
130+
if r < l {
131+
dfs(res, ans+")", l, r+1, n)
132+
}
133+
}
56134
```
57135

58136
### **...**

‎solution/0000-0099/0022.Generate Parentheses/README_EN.md

Lines changed: 79 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -29,13 +29,91 @@
2929
### **Python3**
3030

3131
```python
32-
32+
class Solution:
33+
def generateParenthesis(self, n: int) -> List[str]:
34+
def dfs(ans, l, r, n):
35+
if len(ans) == (n << 1):
36+
self.res.append(ans)
37+
return
38+
if l < n:
39+
dfs(ans + '(', l + 1, r, n)
40+
if r < l:
41+
dfs(ans + ')', l, r + 1, n)
42+
43+
self.res = []
44+
dfs('', 0, 0, n)
45+
return self.res
3346
```
3447

3548
### **Java**
3649

3750
```java
51+
class Solution {
52+
public List<String> generateParenthesis(int n) {
53+
List<String> res = new ArrayList<>();
54+
dfs(res, "", 0, 0, n);
55+
return res;
56+
}
57+
58+
private void dfs(List<String> res, String ans, int l, int r, int n) {
59+
if (ans.length() == (n << 1)) {
60+
res.add(ans);
61+
return;
62+
}
63+
if (l < n) {
64+
dfs(res, ans + "(", l + 1, r, n);
65+
}
66+
if (r < l) {
67+
dfs(res, ans + ")", l, r + 1, n);
68+
}
69+
}
70+
}
71+
```
72+
73+
### **C++**
74+
75+
```cpp
76+
class Solution {
77+
public:
78+
vector<string> generateParenthesis(int n) {
79+
vector<string> res;
80+
dfs(res, "", 0, 0, n);
81+
return res;
82+
}
83+
84+
private:
85+
void dfs(vector<string>& res, string ans, int l, int r, int n) {
86+
if (ans.size() == (n << 1)) {
87+
res.push_back(ans);
88+
return;
89+
}
90+
if (l < n) dfs(res, ans + "(", l + 1, r, n);
91+
if (r < l) dfs(res, ans + ")", l, r + 1, n);
92+
}
93+
};
94+
```
3895
96+
### **Go**
97+
98+
```go
99+
func generateParenthesis(n int) []string {
100+
res := new([]string)
101+
dfs(res, "", 0, 0, n)
102+
return *res
103+
}
104+
105+
func dfs(res *[]string, ans string, l, r, n int) {
106+
if len(ans) == (n << 1) {
107+
*res = append(*res, ans)
108+
return
109+
}
110+
if l < n {
111+
dfs(res, ans+"(", l+1, r, n)
112+
}
113+
if r < l {
114+
dfs(res, ans+")", l, r+1, n)
115+
}
116+
}
39117
```
40118

41119
### **...**

‎solution/0000-0099/0022.Generate Parentheses/Solution.cpp

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
class Solution {
2+
public:
3+
vector<string> generateParenthesis(int n) {
4+
vector<string> res;
5+
dfs(res, "", 0, 0, n);
6+
return res;
7+
}
8+
9+
private:
10+
void dfs(vector<string>& res, string ans, int l, int r, int n) {
11+
if (ans.size() == (n << 1)) {
12+
res.push_back(ans);
13+
return;
14+
}
15+
if (l < n) dfs(res, ans + "(", l + 1, r, n);
16+
if (r < l) dfs(res, ans + ")", l, r + 1, n);
17+
}
18+
};

‎solution/0000-0099/0022.Generate Parentheses/Solution.go

Lines changed: 10 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,18 @@
11
func generateParenthesis(n int) []string {
2-
result := make([]string, 0)
3-
backParenthesis(&result, "", 0, 0, n)
4-
return result
2+
res := new([]string)
3+
dfs(res, "", 0, 0, n)
4+
return *res
55
}
66

7-
func backParenthesis(result *[]string, cur string, open, close, max int) {
8-
if len(cur) == 2 * max {
9-
*result = append(*result, cur)
7+
func dfs(res *[]string, ans string, l, r, n int) {
8+
if len(ans) == (n << 1) {
9+
*res = append(*res, ans)
1010
return
1111
}
12-
13-
if open < max {
14-
backParenthesis(result, cur+"(", open+1, close, max)
12+
if l < n {
13+
dfs(res, ans+"(", l+1, r, n)
1514
}
16-
if close < open {
17-
backParenthesis(result, cur+")", open, close+1, max)
15+
if r < l {
16+
dfs(res, ans+")", l, r+1, n)
1817
}
1918
}

‎solution/0000-0099/0022.Generate Parentheses/Solution.java

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -5,16 +5,16 @@ public List<String> generateParenthesis(int n) {
55
return res;
66
}
77

8-
private void dfs(List<String> res, String ans, int l, int r, int length) {
9-
if (ans.length() == length * 2) {
8+
private void dfs(List<String> res, String ans, int l, int r, int n) {
9+
if (ans.length() == (n << 1)) {
1010
res.add(ans);
1111
return;
1212
}
13-
if (l < length) {
14-
dfs(res, ans + "(", l + 1, r, length);
13+
if (l < n) {
14+
dfs(res, ans + "(", l + 1, r, n);
1515
}
1616
if (r < l) {
17-
dfs(res, ans + ")", l, r + 1, length);
17+
dfs(res, ans + ")", l, r + 1, n);
1818
}
1919
}
20-
}
20+
}

‎solution/0000-0099/0022.Generate Parentheses/Solution.py

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
class Solution:
2+
def generateParenthesis(self, n: int) -> List[str]:
3+
def dfs(ans, l, r, n):
4+
if len(ans) == (n << 1):
5+
self.res.append(ans)
6+
return
7+
if l < n:
8+
dfs(ans + '(', l + 1, r, n)
9+
if r < l:
10+
dfs(ans + ')', l, r + 1, n)
11+
12+
self.res = []
13+
dfs('', 0, 0, n)
14+
return self.res

0 commit comments

Comments
 (0)