吴良超的学习笔记

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)