构造n个成对括号

姘搁『发布于2019-07-30 14:20 / 1887人阅读

摘要：构造个成对括号给出一个整数，实现一个函数生成对小括号，对小括号的左右括弧顺序不限，但应该闭合。思路的情况为时的括号串中在缝隙位置再插入一个括号，如中位置。递归解决，时为在和中再插入一个括号。

构造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地址

超融合服务器 idc机房托管括号里大括号花括号括号

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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