leetcode 22. 括号生成 generate parentheses - python

目录

1. 解答
   1. 递推
   2. 递归

https://leetcode-cn.com/problems/generate-parentheses

解答

递推

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return []
        dp = [[''], ['()']]
        for i in range(2, n+1):
            l = []
            for j in range(i):
                l1 = dp[j]
                l2 = dp[i-j-1]
                for s1 in l1:
                    for s2 in l2:
                        l.append('('+s1+')' + s2)
            dp.append(l)
        return dp[-1]

s1 == '' 时： '()' + s2

s2 == '' 时： '(' + s1 + ')'

递归

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return []
        ans = []
        def dfs(p, left, l):
            if l == n << 1:
                ans.append(p)
                return
            if l + left + 2 <=  n << 1:
                dfs(p + '(', left + 1, l + 1)
                if left > 0:
                    dfs(p + ')', left - 1, l + 1)
            else:
                ans.append(p + ')' * left)
        dfs('(', 1, 1)
        return ans