Login light

https://leetcode-cn.com/problems/generate-parentheses/

题解
https://leetcode-cn.com/problems/generate-parentheses/solution/di-gui-jie-fa-dai-ma-hen-jian-ji-piao-liang-si-lu-/

前言

因为运气好写了个很漂亮的答案,所以想来分享一下。
怕看了题解就懒了,自己想了一天,走了一点弯路。

弯路

最开始我想的是分情况递归,让括号成对匹配,分为三种情况,第一种是左侧右侧添加(),一种是两边加括号。
但是我发现一个特例,括号按对添加无法生成诸如(())(())这种结果。所以这个思路放弃。

解法思路

既然括号无法成对匹配添加,那就只能一个一个添加了,这里一个个添加主要的问题就是怎么保证括号合法。
我这里用计数的方法来实现,左右括号计数变量分别为lr,我列个表看一下就懂了。

结果lr
33
(23
((13
(()12
(())11
(())(01
(())()00

我们能通过上面这个表总结出几个规律。

  1. l <= r 永远成立,因为总要先有(才能有)
  2. l == r 只能添加(
  3. l < r()都可以添加

我们现在可以根据上面的规律,总结出递归的判断条件。

  1. l = 0 and r = 1 返回 ) ,递归返回点
  2. l != 0 返回(
  3. l < r 返回)

根据上面的规律,只需要两个参数就可以写出一个漂亮的递归函数,如下。

代码

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def dp(l: int,r: int):
            ret = []
            if l == 0 and r == 1:
                return [')']
            if l != 0:
                #可以给'('
                for item in dp(l-1,r):
                    ret.append('(' + item)
            if l < r:
                #可以给')'
                for item in dp(l,r-1):
                    ret.append(')' + item)
            return ret
        return dp(n,n)