Sui Xin's Blog

[LeetCode]22. 括号生成（Generate Parentheses）

Posted on In Disqus:

题目描述

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

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

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

解题思路

  1. 解法一：回溯法。分别统计左括号和右括号的数量，左括号小于 n 时，添加左括号，右括号数量少于左括号数量时，添加右括号。
  2. 解法二：递归。相当于写出一对括号 ()，再分别在左括号和右括号后面放置剩下的括号对数。

代码

Python 3.6

解法一：回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def match(s="", left=0, right=0):
            if len(s) == 2 * n:
                res.append(s)
                return
            if left < n:
                match(s + "(", left + 1, right)
            if right < left:
                match(s + ")", left, right + 1)
        match()
        return res

执行用时 : 48 ms
内存消耗 : 14 MB

解法二：递归

1
2
3
4
5
6
7
8
9
10
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return [""]
        res = []
        for i in range(n):
            for left in self.generateParenthesis(i):
                for right in self.generateParenthesis(n - 1 - i):
                    res.append("({}){}".format(left, right))
        return res

执行用时 : 72 ms
内存消耗 : 14.1 MB

参考

https://leetcode-cn.com/problems/generate-parentheses/solution/gua-hao-sheng-cheng-by-leetcode

Related Posts