[Medium]LeetCode#22. 括号生成
这是最近解的一个题目
题目原地址
1
2
3
4
5
6
7
8
9
10
11
| 给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
|
1. 自己原来想的解法，在合适的地方放入一个的完整括号，以保证新生成的序列是有序的，然后通过一个map来保证不重复
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
| func generateParenthesis(n int) []string {
defaultStr := "()"
var str []string
if n == 0 {
str = append(str, "")
}
for i := 0; i < n; i++ {
if len(str) < 1 {
str = append(str, defaultStr)
} else {
var strSub []string
strMap := make(map[string]string)
for _, v := range str {
m := len(v)
for l := 0; l < m; l++ {
a := string(v[l])
b := ""
if l < m-1 && ((a == "(" && string(v[l+1]) == ")") || (a == "(" && string(v[l+1]) == "(")) {
b = string(v[:l+1]) + defaultStr + string(v[l+1:m])
strSub = append(strSub, )
} else if l == m-1 && a == ")" && string(v[l-1]) == "(" {
b = v + defaultStr
}
if _, ok := strMap[b]; !ok && b != "" {
strMap[b] = b
strSub = append(strSub, b)
}
}
}
str = strSub
}
}
return str
}
|
2. 回溯算法，官方解答
思路和算法
只有在我们知道序列仍然保持有效时才添加 ‘(’ or ‘)'，而不是像方法一那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，
如果我们还剩一个位置，我们可以开始放一个左括号。 如果它不超过左括号的数量，我们可以放一个右括号。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| var l int
func backtrack(str *[]string, ans string, open int, close int) {
if len(ans) == 2*l {
*str = append(*str, ans)
return
}
if open < l {
backtrack(str, ans+"(", open+1, close)
}
if open > close {
backtrack(str, ans+")", open, close+1)
}
}
func generateParenthesis(n int) []string {
var str []string
l = n
backtrack(&str, "", 0, 0)
return str
}
|
执拗前行