構造n個成對括號

姘擱『發布于2019-07-30 14:20 / 2020人閱讀

摘要：構造個成對括號給出一個整數，實現一個函數生成對小括號，對小括號的左右括弧順序不限，但應該閉合。思路的情況為時的括號串中在縫隙位置再插入一個括號，如中位置。遞歸解決，時為在和中再插入一個括號。

構造n個成對括號 Generate Parentheses

給出一個整數n，實現一個函數生成n對小括號，n對小括號的左右括弧順序不限，但應該閉合。

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

example 1

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
].

思路

n=2的情況為n=1時的括號串()中在縫隙位置再插入一個括號，如1(2)3中1,2,3位置。可以用set剔除重復元素。

遞歸解決，n=3時為在()()和(())中再插入一個括號。

思路2來源自leetcode討論區，使用open記錄已經有多少左括號，如果n==0，將")" * open閉合。

代碼

class Solution(object):

    def __init__(self):
        self.table = {1: ["()"]}

    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        if n == 1:
            return self.table[1]
        if n-1 in self.table.keys():
            nset = set()
            n1set = self.table[n-1]
            for _, item in enumerate(n1set):
                for j in range(len(item)):
                    nset.add(item[0:j] + "()" + item[j:])
            self.table[n] = list(nset)
            return self.table[n]
        else:
            self.generateParenthesis(n-1)
            return self.generateParenthesis(n)


    def gen2(self, n, open=0):
        if n == 0: return [")"*open]
        if open == 0:
            return ["("+x for x in self.gen2(n-1, 1)]
        else:
            return [")"+x for x in self.gen2(n, open-1)] + ["("+x for x in self.gen2(n-1, open+1)]

本題以及其它leetcode題目代碼github地址: github地址

GPU云服務器云服務器括號里大括號花括號括號

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/40643.html

leetcode32 Longest Valid Parentheses 最長括號組的長度

摘要：題目要求原題地址一個括號序列，求出其中成對括號的最大長度思路一使用堆棧這題可以參考我的另一篇博客這篇博客講解了如何用堆棧判斷括號序列是否可以成對。我們可以將堆棧的思路延續到這里。在這里需要先遍歷一遍字符串，再遍歷一下非空的堆棧。題目要求原題地址：https://leetcode.com/problems... Given a string containing just the c...

happyhuangjinjin 2019-08-14 18:13 評論0 收藏0
leetcode22. Generate Parentheses

摘要：當右括號和左括號的剩余量均為時，及為一個最終結果。而則會在直接原來的對象上進行修改，其指針仍然指向原來的對象。因此在遞歸的過程中使用一定要注意，對對象的修改不要相互干擾。題目要求 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses....

騫諱護 2019-08-14 18:35 評論0 收藏0
驗證大小中括號是否成對閉合匹配

摘要：驗證大小中括號是否成對閉合匹配驗證大小中括號是否成對閉合匹配。驗證大小中括號是否成對閉合匹配 Valid Parentheses 驗證大小中括號是否成對閉合匹配。 Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is valid. The...

QiShare 2019-07-25 12:04 評論0 收藏0
leetcode20 判斷括號是否成對出現

摘要：判斷括號是否成對出現判斷一個字符串中的括號是否成對出現該題的核心思路在于使用棧。判斷括號是否成對出現判斷一個字符串中的括號是否成對出現該題的核心思路在于使用棧。該方法雖然不是最優解但是思路還是比較清晰的 /** * @author rale * Given a string containing just the characters (, ), {, }, [ and ]...

zeyu 2019-08-14 17:50 評論0 收藏0
JS括號匹配問題

摘要：在上做了一道括號匹配的題目。題目判斷字符串中的三種括號是否匹配，需要考慮嵌套的情況。是，則表示完全匹配，否則，比匹配。在codewars上做了一道括號匹配的題目。題目判斷字符串中的{}、[]、()三種括號是否匹配，需要考慮嵌套的情況。例子： validBraces((){}[]) // true validBraces((}) // false va...

lordharrd 2019-08-20 11:38 評論0 收藏0