leetcode中如何实现括号生成

小编给大家分享一下leetcode中如何实现括号生成,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!

目前创新互联公司已为上1000家的企业提供了网站建设、域名、虚拟主机绵阳服务器托管、企业网站设计、阳春网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。

括号生成

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例:输入:n = 3输出:[       "((()))",       "(()())",       "(())()",       "()(())",       "()()()"     ]

考点:dfs或者动态规划

思路

  •     迭代的思想,左右括号的数量关系

  •     动态规划,划分为‘(’ + good_l + ')' + good right

class Solution:    def generateParenthesis(self, n: int) -> List[str]:        if n is None or n < 1:            return []        res = []        # 递归,左右括号的数量        '''        def helper(s, l, r):            if l == 0 and r == 0:                res.append(s)            if l > 0:                helper(s+'(', l-1, r)            if r > l:                helper(s+')', l, r-1)            if r > l:                return         helper('', n, n)        return res        '''        # dp        # 状态转移方程:dp[i] = '(' + dp[j] + ')' + dp[i-j-1]   # 由两部分组成        # dp[i]表示i对括号的有效括号组合        dp = [None] * (n+1)        dp[0] = ['']        for i in range(1, n+1):            cur = []            for j in range(i):                left = dp[j]                right = dp[i-j-1]                for s1 in left:                    for s2 in right:                        cur.append('(' + s1 + ')' + s2)            dp[i] = cur        return dp[n]

以上是“leetcode中如何实现括号生成”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注创新互联行业资讯频道!


文章名称:leetcode中如何实现括号生成
网站网址:http://myzitong.com/article/jjshdc.html