-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathleetcode_22.py
More file actions
40 lines (34 loc) · 899 Bytes
/
leetcode_22.py
File metadata and controls
40 lines (34 loc) · 899 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# coding=utf-8
from typing import List
import sys
from src.data_structure.data_structure import ListNode
class Solution:
"""
括号生成
"""
def generate(self, res: List[str], s: str, left: int, right: int):
"""
:param res:
:param s:
:param left:
:param right:
:return:
"""
if left == 0 and right == 0:
res.append(s)
else:
if left > 0:
self.generate(res, s + "(", left - 1, right)
if right > left:
self.generate(res, s + ")", left, right - 1)
def generate_parenthesis(self, n: int) -> List[str]:
"""
Time: O(4^n / sqrt(n)), Space: O(n) 卡特兰数
:param n:
:return:
"""
res = []
if n <= 0:
return res
self.generate(res, "", n, n)
return res