leetcode题目22. 括号生成

leetcode题目22. 括号生成

题目描述

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

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

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

python代码

'''动态规划：dp[i]表示i组括号的所有有效组合dp[i] = "(dp[p]的所有有效组合)+【dp[q]的组合】"，其中 1 + p + q = i , p从0遍历到i-1, q则相应从i-1到0'''class Solution: def generateParenthesis(self, n: int) -> List[str]: dp = [[] for _ in range(n+1)] # dp[i]存放i组括号的所有有效组合 dp[0] = [""] # 初始化dp[0] for i in range(1, n+1): # 计算dp[i] for p in range(i): # 遍历p l1 = dp[p] # 得到dp[p]的所有有效组合 l2 = dp[i-1-p] # 得到dp[q]的所有有效组合 for k1 in l1: for k2 in l2: dp[i].append("({0}){1}".format(k1, k2)) return dp[n]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。