NeetCode 150 [Stack]:medium 3/5

NeetCodeのSolutionを書いていく

Generate Parentheses

問題概要

整数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