欧酷网

您的位置:主页>算法>

【LeetCode】22.括号生成(Python 版)

题目描述

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

例如,给出 n = 3,生成结果为:

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

思路

方法一:暴力法:枚举出所有的括号组合,再判断其是否有效

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def generate(seq=[]):
            if len(seq) == 2 * n:
                if valid(seq):
                    ans.append("".join(seq))
            else:
                seq.append('(')
                generate(seq)
                seq.pop()
                seq.append(')')
                generate(seq)
                seq.pop()

        def valid(seq):
        # 通过左右括号的数量是否匹配判断序列是否有效
            left = 0
            for c in seq:
                if c == '(':
                    left += 1
                else:
                    left -= 1
                # left 小于 0 说明出现了右括号在左括号之前
                if left < 0:
                    return False
            return left == 0

        ans = []
        generate()
        return ans
 

方法二:回溯法(其实也是一种DFS):
暴力方法的过程中会生成很多很显然不正确的序列,例如’((((((’,但从左右括号数量上看就不符合。为了减少不必要的序列城市,将检查有效性提前,只有当序列当前有效时才继续添加’(‘或者’)’。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def backtrack(prefix, left, right):
            if len(prefix) == 2 * n:
                res.append(prefix)
                return
            # 控制左括号的数量,避免出现'(((((('的情况
            if left < n:
                backtrack(prefix + '(', left + 1, right)
            # 控制右括号的数量
            if right < left:
                backtrack(prefix + ')', left, right + 1)
        backtrack('', 0, 0)
        return res
 

方法三:动态规划法(官方题解称为闭合数):
假如我们已经知道 n=i 时的所有有效括号组合,用 S 表示其中任意一个组合,那么n=i+1 时的所有有效括号应该如何计算?是        (+S+)‘(’+S+‘)’,还是        (+)+S‘(’+‘)’+ S,甚至可以是        (+Sleft+)+Sright‘(’+S_{left}+‘)’+S_{right}

其实第三种表示方法已经包含了前两种情况(当        Sleft==SS_{left} == S时为第一种,当        Sright==SS_{right} == S时为第二种)。更有意思的是第三种表示方法实际上包含了 n=i+1 时的所有有效括号序列,其中        SleftSrightS_{left}和S_{right}分别是 n=pn=q 时的有效括号序列,约束条件是 p+q=i

:可能有人认为        Sleft+(+)+SrightS_{left}+‘(’+‘)’+S_{right}不被包含在内,这里解释一下,单看        SleftS_{left},既然是有效的序列,那么它的第一个字符必然是‘(’,那么        Sleft+(S_{left}+‘(’        (+Sleft‘(’+S_{left}其实是一样的。

这里用dp[i]表示 n=i 时的所有有效括号组合,那么状态转移公式为        dp[i+1]=(+Sleft+)+Sright=(+dp[p]+)+dp[ip]p=0,1,2,...idp[i+1] = ‘(’+S_{left}+‘)’+S_{right} = ‘(’+dp[p]+‘)’+dp[i-p],p = 0,1,2,...i

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        dp = [[] for _ in range(n + 1)]
        dp[0] = ['']
        for i in range(1, n + 1):
            for p in range(i):
                left = dp[p]
                right = dp[i - 1 - p]
                for left_seq in left:
                    for right_seq in right:
                        dp[i].append('(' + left_seq + ')' + right_seq)
        return dp[-1]
  • 点赞

  • 收藏

  • 分享

  •    
    • 文章举报

一颗随风而倒的墙头草

 
发布了57 篇原创文章 ·    获赞 12 ·    访问量 2万+  

私信

关注

相关文章推荐