0022 - Generate Parentheses
题干
破题
额，测试用例就是题目限制的 $8$ 个。
解①直接构造：
直接构造所有可能的字符串，从空串开始逐个增加字符，( 和 ) ，直到字符串长度达到 $2n$ 。
- 左括号可以随意增加，只要总数不超过 $n$
- 右括号必须匹配一个左括号，不能随意增加，它的数量不能超过当前左括号的数量
from typing import List
def solve(n: int) -> List[str]:
ans = []
def build(s: str, open: int, close: int):
if len(s) ==n * 2:
ans.append(s)
return
if close == open:
build(s+'(', open+1, close)
elif open == n:
build(s+')', open, close+1)
else:
build(s+'(', open+1, close)
build(s+')', open, close+1)
build("", 0, 0)
return ans
思路是本题最佳实现，$45$ ms ，虽然没有 beats 100% ，但和最快的例子没有区别
解②树级构造：
本题有一个 DP 的标签，从一开始考虑得是如果利用之前的构造进行构造。
发现了这样一个办法：每个可能的串都由并列的几个括号单元组成，比如 (()())(()) 就有两个括号单元 (()()) 和 (()) ，长度为 $n$ 的括号组合可以由长度为 $n-1$ 的括号组合按照每一个括号单元外面镶嵌一层括号，每两个括号单元外镶嵌括号，… ，每 $n$ 个括号单元外镶嵌括号，以及不镶嵌括号，增加一个新的并列括号单元。
不过这种构造方法会构造出重复的情况，而且没法儿简单判断，最佳方法还是放入 set 里过滤一遍。
数据结构：
考虑下括号单元的表示形式，最简单地是 Leaf() ，表示最基本的 ()，直接使用单例模式（singleton）表示，而括号单元列表的括号嵌套就是 Branch ，为了用哈希集合过滤重复元素，特别定义了 Branch 的哈希方法 __hash__ 和正确处理哈希冲突需要的判等方法 __eq__ 。
class Leaf:
def __len__(self):
return 2
def __repr__(self) -> str:
return '()'
class Branch: pass
class Branch:
def __init__(self, children: List[Leaf | Branch]) -> None:
self.children = children
self.repr = '({})'.format(
''.join([repr(child) for child in self.children])
)
self.hash = hash(self.repr)
def __repr__(self) -> str:
return self.repr
def __hash__(self):
return self.hash
def __eq__(self, other: object) -> bool:
return repr(self) == repr(other)
leaf = Leaf()
parens = [
{(leaf,)}, # {()}
{(Branch([leaf]),), (leaf, leaf)} # {(()), ()()}
]
计算过程：
def solve(n: int) -> List[str]:
for i in range(len(parens), n):
parens.append(set(gen_paren_comb(i-1)))
return [''.join([repr(part) for part in parts]) for parts in parens[n-1]]
def gen_paren_comb(prev_i: int):
for parts in parens[prev_i]:
# nested on each parens units: 1~n
for k in range(len(parts), 0, -1):
for j in range(0, len(parts)-k+1):
yield parts[:j] + (Branch(parts[j:j+k]),) + parts[j+k:]
yield (leaf,) * (prev_i+2)
在本题情况下不如直接递归地构造，运行时间 $59$ ms 。
注解
