leetcode 22. Generate Parentheses#python

xiaoxiao2021-02-28  23

本题之前一直纠结如何循环调用,后来看网上思路有人用到递归,整理后的代码如下,

基本思路是:

1.左边括号数要大于右边括号数

2.在1的原则下,每次递归为字符串赋值"("或")"

3.每次递归生成两个分支,分别往下去找,最终找到所有组合

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

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

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

class Solution(object):     def func(self,array,string,left,right):         """array:最终生成的list            string:本轮已经完成的str            left:左括号剩余个数            right:右括号剩余个数         """         if left == 0 and right == 0:#递归终止条件,左边括号与右边括号剩余个数均为0             array+=[string]         if left > 0:#左边括号剩余大于0,则可以继续往下递归             self.func(array,string+"(",left-1,right)         if right > 0 and left<right:#右边括号剩余大于0且左边剩余小于右边剩余,则可继续递归             self.func(array,string+")",left,right-1)                  def generateParenthesis(self, n):         """         :type n: int         :rtype: List[str]         """         rtn = []         self.func(rtn,"",n,n)         return rtn                      

贴上乔同学的非递归方式

转载请注明原文地址: https://www.6miu.com/read-1949967.html

最新回复(0)