leetcode中如何實現(xiàn)括號生成

發(fā)布時間：2022-01-05 16:20:07 來源：億速云閱讀：117 作者：小新欄目：大數(shù)據(jù)

小編給大家分享一下leetcode中如何實現(xiàn)括號生成，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

括號生成

數(shù)字 n 代表生成括號的對數(shù)，請你設(shè)計一個函數(shù)，用于能夠生成所有可能的并且有效的括號組合。

示例：輸入：n = 3輸出：[       "((()))",       "(()())",       "(())()",       "()(())",       "()()()"     ]

考點：dfs或者動態(tài)規(guī)劃

思路：

迭代的思想，左右括號的數(shù)量關(guān)系
動態(tài)規(guī)劃，劃分為‘(’ + good_l + ')' + good right

class Solution:    def generateParenthesis(self, n: int) -> List[str]:        if n is None or n < 1:            return []        res = []        # 遞歸，左右括號的數(shù)量        '''        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        # 狀態(tài)轉(zhuǎn)移方程：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]

以上是“l(fā)eetcode中如何實現(xiàn)括號生成”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道！

向AI問一下細節(jié)

leetcode中如何實現(xiàn)括號生成

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標簽