题目:
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例:
输入:n = 3
输出:[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
题目的理解:
写成当n为1,2,3,4后,总结出规律为 f(3) = f(1) * f(2) + f(1)中间插入f(2)。使用递归就可以实现逻辑。
python实现
from typing import List
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
self.processing = dict()
def recursion(num: int) -> set:
if 1 == num:
return {'()'}
if num in self.processing.keys():
return self.processing[num]
temp_set = set()
for index in range(1, num):
left = recursion(index)
right = recursion(num - index)
for item1 in left:
for item2 in right:
half = len(item1) // 2
item3 = item1[:half] + item2 + item1[half:]
temp_set.add(item1 + item2)
temp_set.add(item3)
self.processing[num] = temp_set
return temp_set
return list(recursion(n))
想看最优解法移步此处
提交
ok难得一次通过,看着很难的题目,当发现规律后还是很清晰的。
// END 每天过的开心,做自己喜欢做的事
网友评论