[Swift]LeetCode22.括号生成|GenerateParentheses

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9890477.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

【回溯法】思路和算法

只有在我们知道序列仍然保持有效时才添加 '(' or ')'，而不是像方法一那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，

如果我们还剩一个位置，我们可以开始放一个左括号。如果它不超过左括号的数量，我们可以放一个右括号。

 1 class Solution {
 2     func generateParenthesis(_ n: Int) -> [String] {
 3         var ans:[String] = [String]()
 4         backtrack(&ans, "", 0, 0, n)
 5         return ans
 6     }
 7     
 8     func backtrack(_ ans: inout [String], _ cur:String, _ open:Int, _ close:Int, _ max:Int)
 9     {
10         if cur.count == max * 2
11         {
12             ans.append(cur)
13             return
14         }
15         if open < max
16         {
17             backtrack(&ans, cur+"(", open+1, close, max)
18         }
19         if close < open
20         {
21             backtrack(&ans, cur+")", open, close+1, max)
22         }
23     }
24 }

【闭合数】思路

为了枚举某些内容，我们通常希望将其表示为更容易计算的不相交子集的总和。

考虑有效括号序列 S 的闭包数：至少存在index> = 0，使得 S[0], S[1], ..., S[2*index+1]是有效的。显然，每个括号序列都有一个唯一的闭包号。我们可以尝试单独列举它们。

算法

对于每个闭合数 c，我们知道起始和结束括号必定位于索引 0 和 2*c + 1。然后两者间的 2*c 个元素一定是有效序列，其余元素一定是有效序列。

 1 class Solution {
 2     func generateParenthesis(_ n: Int) -> [String] {
 3         var ans:[String] = [String]()
 4         if n == 0
 5         {
 6             ans.append("")
 7         }
 8         else
 9         {
10             for c in 0..<n
11             {
12                 for left in generateParenthesis(c)
13                 {
14                     for right in generateParenthesis(n-1-c)
15                     {
16                         ans.append("(" + left + ")" + right)
17                     }
18                 }
19             }
20         }
21         return ans
22     }
23 }

8ms

 1 class Solution {
 2     func generateParenthesis(_ n: Int) -> [String] {
 3         var output: [String] = []
 4         
 5         handler(output: &output, n: n, left: 0, right: 0, text: "")
 6         
 7         return output
 8     }
 9     
10     func handler(output: inout [String], n: Int, left: Int, right: Int, text: String) {
11         // print("left: \(left), right: \(right)")
12         
13         if(left == n && right == n) {
14             output.append(text)
15             return
16         }
17 
18         if(left <= n && left > right) {
19             handler(output: &output, n: n, left: left, right: right + 1, text: text + ")")
20         }
21         
22         if(left < n) {
23             handler(output: &output, n: n, left: left + 1, right: right, text: text + "(")
24         }
25         
26     }
27 }

12ms

 1 class Solution {
 2     func generateParenthesis(_ n: Int) -> [String] {
 3         var ss = [String]()
 4         generate(ss: &ss, s: "", open: 0, close: 0, n: n)
 5         return ss
 6     }
 7 
 8     private func generate(ss: inout [String], s: String, open: Int, close: Int, n: Int) {
 9         if s.count == n * 2 && !s.isEmpty {
10             ss.append(s)
11         }
12         if open < n {
13             generate(ss: &ss, s: "\(s)(", open: open+1, close: close, n: n)
14         }
15         if close < open {
16             generate(ss: &ss, s: "\(s))", open: open, close: close+1, n: n)
17         }
18     }
19 }

12ms

 1 class Solution {
 2     func generateParenthesis(_ n: Int) -> [String] {
 3         guard n > 0 else {
 4             return []
 5         }
 6         var result = [String]()
 7         
 8         dfs(left: 0, right: 0, buffer: "", result: &result, n: n)
 9         
10         return result
11     }
12 
13     func dfs(left: Int, right: Int, buffer: String, result: inout [String], n: Int) {
14         if left == n && right == n {
15             result.append(buffer)
16             return
17         }
18         
19         if left < n {
20             dfs(left: left + 1, right: right, buffer: buffer + "(", result: &result, n: n)
21         }
22         
23         if left > right {
24             dfs(left: left, right: right + 1, buffer: buffer + ")", result: &result, n: n)
25         }
26     }
27 }

20ms

 1 class Solution {
 2     func generateParenthesis(_ n: Int) -> [String] {//闭合数
 3         return generateBracket(n)
 4     }
 5 
 6     func generateBracket(_ n: Int) -> [String] {
 7         if n <= 0 {
 8             return [""]
 9         }
10         
11 
12         var bracket : [String] = []
13         
14         for idx in 0..<n {
15             for left in generateBracket(idx) {
16                 for right in generateBracket(n-idx-1) {
17                     bracket.append("(\(left))\(right)")
18                 }
19             }
20         }
21         
22         return bracket
23     }
24 }

24ms

 1 class Solution {
 2     func generateParenthesis(_ n: Int) -> [String] {
 3         if n == 0 {return []}
 4         return dfs("",  n, n)
 5     }
 6 
 7     //遍历叶子节点
 8     func dfs(_ head:String, _ left:Int, _ right:Int) -> [String] {
 9         if left == 0 && right == 0 { 
10             return [head] 
11         }
12         var res = [String]()
13         if left > 0 {   
14             res = res + dfs(head + "(", left-1, right) 
15         }
16         if right > left  { 
17             res = res + dfs(head + ")", left, right-1) 
18         }
19         return res
20     }
21 }

44ms

 1 class Solution {
 2 enum Paren: String {
 3   case o = "("
 4   case c = ")"
 5 }
 6 
 7 class TreeNode {
 8   let val: Paren
 9   var left: TreeNode?
10   var right: TreeNode?
11   
12   init(val: Paren) {
13     self.val = val
14   }
15   
16   func treeValues() -> [String] {
17     // DFS walk the tree multiple times to print out the tree
18     guard (self.left != nil) || (self.right != nil) else {
19       return [self.val.rawValue]
20     }
21     
22     var res = [String]()
23     for node in [self.left, self.right] {
24       if let node = node {
25         for s in node.treeValues() {
26           res.append(self.val.rawValue + s)
27         }
28       }
29     }
30     return res
31   }
32 }
33 
34 func populateTree(root: TreeNode, maxOpenParens: Int, availOpenParens: Int, availClosedParens: Int) {
35   // Implement a BST
36   if availOpenParens > 0 { 
37     root.left = TreeNode(val: Paren.o)
38     populateTree(root: root.left!, maxOpenParens: maxOpenParens, availOpenParens: availOpenParens - 1, availClosedParens: availClosedParens + 1)
39   }
40   if availClosedParens > 0 { 
41     root.right = TreeNode(val: Paren.c)
42     populateTree(root: root.right!, maxOpenParens: maxOpenParens, availOpenParens: availOpenParens, availClosedParens: availClosedParens - 1)
43   }
44 }
45 
46 func generateParenthesis(_ n: Int) -> [String] {
47     let root = TreeNode(val: Paren.o)
48     populateTree(root: root, maxOpenParens: n, availOpenParens: n - 1, availClosedParens: 1)
49     return root.treeValues()
50   }
51 }