LeetCode 解题报告(22)--生成所有合法的嵌套括号

发表于 标签 ，

原题如下： >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: "((()))", "(()())", "(())()", "()(())", "()()()"

题目要求生成给定数量的所有合法嵌套括号，最直观的想法是通过穷举得到所有的组合结果，再判断每个是否合法，但是这样的时间复杂度太大，会导致TLE。

既然上面的方法会导致TLE, 那么能不能在构造的过程中判断目前所构造的嵌套括号是否合法？

答案是可以的，只需要遵循以下的两条规则即可: 1.只要"("的数量没有超过n，都可以插入"("。 2.而可以插入")"的前提则是当前的"("数量必须要多余当前的")"数量。

通过回溯法能够实现这个判断并构造出所有合法的嵌套括号，实现代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        res = []
        self.helper(n,n,'',res)
        return res
        
    def  helper(self,left,right,item,res):
        if left==0 and right==0:
            res.append(item)
            return
        if left>0:
            self.helper(left-1,right,item+'(',res)
        if right>left:
            self.helper(left,right-1,item+')',res)