Generate Parentheses

Q: Generate Parentheses の時間計算量は何ですか？

バックトラッキングによる解法は、カタラン数 C(n) = (2n)! / ((n+1)! n!) 個の文字列を出力します。この数は 4^n / (n^1.5 √π) のように増加します。各文字列の長さは 2n で、探索では無駄な分岐がないため、全体の時間計算量は O(4^n / √n) です。追加の空間計算量は、現在の文字列と呼び出しスタックに対して O(n) であり、これに出力分が加わります。

Q: n 組のかっこに対して、有効なかっこ文字列はいくつありますか？

ちょうどn番目のカタラン数です。 n が1から8の場合、1、2、5、14、42、132、429、1,430です。これを見る方法の一つは、すべての整形式文字列が ( + A + ) + Bであり、最初の ( はその ) と対応し、AとBは合わせて n-1 組の括弧を含む整形式文字列であると考えることです。Aのサイズについて合計すると、カタラン数の漸化式が得られます。

Q: なぜ closed < opened なら有効な文字列が保証されるのでしょうか？

文字列が不正になるのは、対応する ( が先に現れていない状態で ) が現れたとき、つまり ) の数が ( の数を上回るときです。 closed < opened の場合にのみ ) を許可すれば、これを防げます。また、 opened < n の場合にのみ ( を許可すれば、長さが 2n になった時点で両方の数が n に達します。この2つのルールを合わせると、整形式の文字列のすべての接頭辞を表せます。

Q: Generate Parentheses は再帰を使わずに解けますか？

はい。部分状態をスタックに保持します。それぞれの状態は、2つのカウンターを含む文字列です。そして、同じ2つのルールで状態を拡張します。 ) の拡張を ( の拡張より先にプッシュすると、 ( の方が先にポップされ、出力はソートされたままになります。作業量は同じで、管理する場所が呼び出しスタックから自分で用意したスタックに移るだけです。

ふつうバックトラッキング再帰

+10

括弧の文字列は、左から右に読んだとき、)の数が(の数を上回らず、最後に2つの数が等しければ、正しい形式です。したがって、(())()は正しい形式ですが、())(は正しくありません。3文字目が、開かれていない括弧のペアを閉じているためです。

整数nが与えられます。n個の開き括弧とn個の閉じ括弧からなる、正しい形式の文字列をすべて、(が)より前になる辞書順で並べて返してください。

関数

generateParenthesis(n: integer) → string-array

ninteger: 括弧のペアの数
戻り値string-array: n組のすべての整形式文字列を辞書順に

制約

1 ≤ n ≤ 8
n = 8の場合、答えは1,430個の文字列です。

例

入力: n = 3
出力: ["((()))", "(()())", "(())()", "()(())", "()()()"]
説明: 3組は、正しい形式で5通りに並べられます。((()))は、どれも閉じる前に3組すべてを開き、(はソート順で先になるため、リストの先頭になります。()()()は各組をすぐに閉じるため、最後になります。

入力: n = 1
出力: ["()"]
説明: 1組のペアには、正しい並び方が1つあります。(と)が1つずつ含まれるもう1つの文字列は)(ですが、これは何かが開かれる前に閉じてしまいます。

提出時に隠しテスト+10件

発展問題

生成せずに、n組の整形式文字列の個数を数えられますか？

ヒント

1つずつ開いてください。開くたびに少しずつ答えに近づきます。

3個中0個を表示

解説

長さ 2n の文字列のうち、正しい形式になっているものはごくわずかです。n = 3 では64個中5個、n = 8 では65,536個中1,430個です。この問題を解くには、文字列を左から右へ作り、正しい形式を保てる文字だけを追加します。そうすれば、最後まで完成できない分岐には探索が進みません。何を追加できるかは、( をいくつ置いたか、そして ) をいくつ置いたかという2つのカウンターで決まります。各ステップで ) より先に ( を試すと、文字列は最初からソートされた順に生成されます。

すべての文字列を構築してから、確認しましょう

考え方

直接的な方法は、2n 個の位置をあらゆる方法で埋め、正しい形式の文字列を残すことです。各位置には(または)が入るため、文字列は2^(2n) = 4^n個あります。再帰関数で次の位置に(を置いて再帰し、その後そこに)を置いて再び再帰します。そして、完成した各文字列を検査します。

検査では、残高を使って文字列をたどります。(では1を足し、)では1を引きます。残高が決して0未満にならず、最後に0になれば、その文字列は正しい形式です。残高が0未満になるのは、閉じる対象の開き括弧がないのに)が現れる場合です。たとえば、())(の3文字目がそうです。

各位置で)より先に(を試すと、(は)より辞書順で前に来るため、文字列は辞書順に並びます。したがって、残された文字列はすでにソートされています。

計算量は、4^n個の文字列それぞれをO(n)で検査することです。n = 8の場合、答えは1,430個なのに文字列は65,536個あり、作業のおよそ98%が無駄になります。nが最大8なのでここでは処理が終わりますが、ペアが1つ増えるごとに4倍に増加します。また、最初の文字ですでに不適切だとわかるにもかかわらず、)で始まる文字列も作り続けます。

アルゴリズム

2n 文字のバッファと、答えを格納するリストを用意します。
fill(pos) を作成します。pos が 2n に等しい場合、バッファをチェックし、正しい形式であれば保存します。
そうでなければ、pos に ( を入れて fill(pos + 1) を呼び出し、次に同じ位置に ) を入れて、もう一度呼び出します。
文字列をチェックするには、( ごとに 1 を加算し、) ごとに 1 を減算します。残高が 0 未満になった時点で、または最後に 0 にならなかった場合は、その文字列を除外します。
fill(0) を呼び出し、すでにソートされた保存済みの文字列を返します。

def generateParenthesis(n):
    result = []
    path = []

    def is_balanced(text):
        balance = 0
        for ch in text:
            balance += 1 if ch == "(" else -1
            if balance < 0:
                return False  # a ")" with nothing open to close
        return balance == 0

    def fill():
        if len(path) == 2 * n:
            text = "".join(path)
            if is_balanced(text):
                result.append(text)
            return
        for ch in "()":  # "(" first keeps the output sorted
            path.append(ch)
            fill()
            path.pop()

    fill()
    return result

開く数と閉じる数をバックトラックする

考え方

チェックを構築処理に組み込みます。ある接頭辞が整形式の文字列に成長できるのは、2つの条件を満たす場合に限られます。開き括弧の数が最大でも n 個であり、) の数が ( の数を決して超えないことです。したがって、各ステップでは opened < n のとき ( を追加でき、closed < opened のとき ) を追加できます。文字列の長さが 2n になれば、どちらの数も n となり、文字列は整形式です。もう確認することはありません。

n = 2 の場合のツリー全体を見てみましょう。空文字列からは、まだ何も開いていないため、( だけが許されます。( からは、どちらも許されます。(( の枝では、opened がすでに 2 なので、) だけが適合し、それを2回追加すると (()) になります。() の枝では、何も開いていないため、( だけが適合し、続いて ) を追加すると ()() になります。すべての枝は答えにたどり着きます。探索で、あとから捨てなければならない文字列が作られることはありません。

答えを見落とすこともありません。整形式の文字列のすべての接頭辞は両方の条件を満たすため、探索がその文字列に次に必要な文字を拒むことはありません。また、各文字列は一度だけ生成されます。文字列の文字がツリー内の一つの経路を示すからです。順序は最初の方法と同じです。2つの文字列は経路が分岐する箇所で初めて異なり、その箇所では ( の枝が先に探索されます。

すべての葉は答えであり、n 組に対する答えの数はカタラン数 C(n) で、4^n / (n^1.5 √π) のように増加します。各内部ノードは少なくとも1つの葉へ至る経路上にあるため、答え1つあたりの内部ノードは最大でも 2n 個です。また、答えのコピーには O(n) のコストがかかります。合計は O(n × C(n)) = O(4^n / √n) です。n = 8 の場合、65,536個を検査する代わりに、1,430個の文字列を直接構築できます。

アルゴリズム

構築中の文字列と、opened、closedという2つのカウンターを保持し、どちらも0にします。
文字列の長さが2nになったら、そのコピーを保存して返します。
opened < nの場合、(を追加し、opened + 1で再帰し、追加した文字を削除します。
closed < openedの場合、)を追加し、closed + 1で再帰し、追加した文字を削除します。
空文字列から開始し、保存した文字列を返します。(を先に試すため、すでにソートされています。

def generateParenthesis(n):
    result = []
    path = []

    def backtrack(opened, closed):
        if len(path) == 2 * n:
            result.append("".join(path))
            return
        # "(" sorts before ")", so trying it first keeps the output sorted
        if opened < n:
            path.append("(")
            backtrack(opened + 1, closed)
            path.pop()
        if closed < opened:  # only close a pair that is open
            path.append(")")
            backtrack(opened, closed + 1)
            path.pop()

    backtrack(0, 0)
    return result

落とし穴と境界ケース

この規則は2つの比較で表せるため、バグはその比較と2つの分岐の順序に潜んでいます。

closed < openedではなくclosed < nのときに)を許すと、())(のような文字列が作られ、開かれていないペアを閉じてしまいます。
文字列に(と)が同じ数だけ含まれていることだけを確認すると、)(も受け入れてしまいます。残高は最後だけでなく、各ステップで0以上を保つ必要があります。
(より先に)を試すと、正しい文字列が逆順に生成され、ソート済みの答えとの比較に失敗します。
リストや文字列ビルダーが変更可能な言語で、コピーではなく共有バッファーを保存してしまうと、保存したすべての答えが同じバッファーを参照し、バックトラッキングによってそのバッファーが再び空になります。
2n個の答え、またはその他の小さな推測値で固定サイズの結果配列を確保してしまうことです。n = 8の場合、答えは1,430個あります。配列を拡張するか、先にカタラン数を計算してください。

よくある質問4

Generate Parentheses の時間計算量は何ですか？

バックトラッキングによる解法は、カタラン数 C(n) = (2n)! / ((n+1)! n!) 個の文字列を出力します。この数は 4^n / (n^1.5 √π) のように増加します。各文字列の長さは 2n で、探索では無駄な分岐がないため、全体の時間計算量は O(4^n / √n) です。追加の空間計算量は、現在の文字列と呼び出しスタックに対して O(n) であり、これに出力分が加わります。

n 組のかっこに対して、有効なかっこ文字列はいくつありますか？

ちょうどn番目のカタラン数です。nが1から8の場合、1、2、5、14、42、132、429、1,430です。これを見る方法の一つは、すべての整形式文字列が( + A + ) + Bであり、最初の(はその)と対応し、AとBは合わせてn-1組の括弧を含む整形式文字列であると考えることです。Aのサイズについて合計すると、カタラン数の漸化式が得られます。

なぜ <code>closed</code> < <code>opened</code> なら有効な文字列が保証されるのでしょうか？

文字列が不正になるのは、対応する ( が先に現れていない状態で ) が現れたとき、つまり ) の数が ( の数を上回るときです。closed < opened の場合にのみ ) を許可すれば、これを防げます。また、opened < n の場合にのみ ( を許可すれば、長さが 2n になった時点で両方の数が n に達します。この2つのルールを合わせると、整形式の文字列のすべての接頭辞を表せます。

Generate Parentheses は再帰を使わずに解けますか？

はい。部分状態をスタックに保持します。それぞれの状態は、2つのカウンターを含む文字列です。そして、同じ2つのルールで状態を拡張します。)の拡張を(の拡張より先にプッシュすると、(の方が先にポップされ、出力はソートされたままになります。作業量は同じで、管理する場所が呼び出しスタックから自分で用意したスタックに移るだけです。

Python

def generateParenthesis(n):
    # ここにコードを書いてください

テストケース

ケース1

ケース2

入力

n = 3

期待値

["((()))", "(()())", "(())()", "()(())", "()()()"]

Generate Parentheses

関数

制約

例

ヒント

解説

すべての文字列を構築してから、確認しましょう

開く数と閉じる数をバックトラックする

落とし穴と境界ケース

よくある質問4

似た問題