摘要:构造个成对括号给出一个整数,实现一个函数生成对小括号,对小括号的左右括弧顺序不限,但应该闭合。思路的情况为时的括号串中在缝隙位置再插入一个括号,如中位置。递归解决,时为在和中再插入一个括号。
构造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地址
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/40643.html
摘要:题目要求原题地址一个括号序列,求出其中成对括号的最大长度思路一使用堆栈这题可以参考我的另一篇博客这篇博客讲解了如何用堆栈判断括号序列是否可以成对。我们可以将堆栈的思路延续到这里。在这里需要先遍历一遍字符串,再遍历一下非空的堆栈。 题目要求 原题地址:https://leetcode.com/problems... Given a string containing just the c...
摘要:当右括号和左括号的剩余量均为时,及为一个最终结果。而则会在直接原来的对象上进行修改,其指针仍然指向原来的对象。因此在递归的过程中使用一定要注意,对对象的修改不要相互干扰。 题目要求 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses....
摘要:验证大小中括号是否成对闭合匹配验证大小中括号是否成对闭合匹配。 验证大小中括号是否成对闭合匹配 Valid Parentheses 验证大小中括号是否成对闭合匹配。 Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is valid. The...
摘要:判断括号是否成对出现判断一个字符串中的括号是否成对出现该题的核心思路在于使用栈。 判断括号是否成对出现 判断一个字符串中的括号是否成对出现该题的核心思路在于使用栈。 该方法虽然不是最优解 但是思路还是比较清晰的 /** * @author rale * Given a string containing just the characters (, ), {, }, [ and ]...
阅读 2873·2021-11-23 09:51
阅读 3390·2021-11-22 09:34
阅读 3270·2021-10-27 14:14
阅读 1474·2019-08-30 15:55
阅读 3329·2019-08-30 15:54
阅读 1047·2019-08-30 15:52
阅读 1864·2019-08-30 12:46
阅读 2828·2019-08-29 16:11