# LeetCode22 生成所有括号对

2019/04/10 10:10

<br>

## 链接

Generate Parentheses

<br>

## 难度

<font color=orange>Medium</font>

<br>

## 描述

<br>

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:

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


<br>

<br>

<br>

## 暴力

<br>

def dfs(pos, left, right, n, ret, cur_str):
"""
pos: 当前枚举的位置
left: 已经放置的左括号的数量
right: 已经放置的右括号的数量
n: 括号的数量
ret: 放置答案的数组
cur_str: 当前的字符串
"""
if pos == 2*n:
ret.append(cur_str)
return
if left < n:
dfs(pos+1, left+1, right, n, ret, cur_str+'(')
if right < n:
dfs(pos+1, left, right+1, n, ret, cur_str+')')


<br>

## 优化

<br>

def dfs(pos, left, right, n, ret, cur_str):
"""
pos: 当前枚举的位置
left: 已经放置的左括号的数量
right: 已经放置的右括号的数量
n: 括号的数量
ret: 放置答案的数组
cur_str: 当前的字符串
"""
if pos == 2*n:
ret.append(cur_str)
return
if left < n:
dfs(pos+1, left+1, right, n, ret, cur_str+'(')
if right < n and right < left:
dfs(pos+1, left, right+1, n, ret, cur_str+')')


<br>

## 构造

<br>

$$solution(n) = \sum_{i=1}^{n-1} solution(i)+solution(n-i) + ( + solution(n-1) + )$$

class Solution:

def generateParenthesis(self, n: int) -> List[str]:
solutionMap = {}
# 记录下n=0和1时的答案
solutionMap[0] = set([""])
solutionMap[1] = set(["()"])

# 遍历小于n的所有长度
for i in range(2, n+1):
cur = set()
# 遍历小于n的所有长度
for j in range(1, i):
# 构造答案
ans1 = solutionMap[j]
ans2 = solutionMap[i-j]
for s in ans1:
for t in ans2:
# 构造 ( solution(n-1) )这种答案
for s in solutionMap[i-1]:
solutionMap[i] = cur
return list(solutionMap[n])


0
0 收藏

0 评论
0 收藏
0