NeetCodeのSolutionを書いていく #
Generate Parentheses #
https://neetcode.io/problems/generate-parentheses
neetcode.io
問題概要 #
整数nが与えられます。n個の括弧のペアで作れる括弧の文字列を返しなさい。
- 制約
- nは1以上7以下
計算量：O(4^n / sqrt(n)) メモリ：O(n)
例 #
Input: n = 1 Output: ["()"]
Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]
メモ #
計算オーダーの記載がすごい。 例えば4だと、4^4/sqrt(4) = 128回の計算でできるということか。
相変わらずわからない。。。 ヒントを見ると、カッコが有効な場合のみを探して正解に足していけば良いとのこと。 ループが描きづらいので再帰関数で書いてみる。 かなり汚いができた！
from typing import List
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
result = []
def func(s: str | None, n: int, open: int, close: int):
if s is None:
return
for p in ["(", ")"]:
if p == "(":
op = open + 1
if op > n:
op -= 1
func(None, n, op, close)
else:
func(s + p, n, op, close)
else:
cl = close + 1
if open < cl:
cl -= 1
func(None, n, open, cl)
else:
s += p
if (open + cl) == 2 * n:
result.append(s)
else:
func(s, n, open, cl)
func("", n, 0, 0)
return result