概述
力扣算法:括号生成
- 一、括号生成
- 1、问题
- 2、思路
- 3、代码
- 4、时间与空间复杂度
- 备注
一、括号生成
1、问题
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足:左括号必须以正确的顺序闭合。
示例 1:
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入:n = 1
输出:["()"]
提示:
- 1 <= n <= 8
2、思路
任何一个括号序列都一定是由 " ( " 开头,并且第一个 " ( " 一定有一个唯一与之对应的 )。这样一来,我们只需要考虑 i=n 时相比 i=n-1 时 “增加的那一组括号” 的位置是“添加在括号里面”、还是“添加在括号外面”。
每一个括号序列可以用 “( p ) q” 来表示,其中 p 与 q 分别是一个合法的括号序列(也可以为空)。
- dp[i] 表示 i 组括号的所有有效组合
- dp[i] = “( 【dp[p] 的所有有效组合】) +【dp[q] 的所有有效组合】”,其中 1 + p + q = i , p 从 0 遍历到 i-1 , q 则相应从 i-1 到 0
3、代码
#coding:utf-8
from typing import List
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]
if __name__ == "__main__":
n = 3
s = Solution()
print(s.generateParenthesis(n))
4、时间与空间复杂度
时间复杂度: O ( 4 n n ) O( dfrac{4^n }{sqrt{n}} ) O(n4n)
空间复杂度: O ( 4 n n ) O( dfrac{4^n }{sqrt{n}} ) O(n4n)
备注
1、“问题”转载于:
力扣(LeetCode)
2、参考:
【最简单易懂的】动态规划
最后
以上就是满意香烟为你收集整理的力扣算法:括号生成一、括号生成备注的全部内容,希望文章能够帮你解决力扣算法:括号生成一、括号生成备注所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复