Generate Parentheses
左から右に読んだとき、)の個数が(の個数を上回ることがなく、最後に両者の個数が等しい場合、括弧の文字列は整形式です。したがって、(())()は整形式ですが、())(はそうではありません。3文字目が、対応する開き括弧のない閉じ括弧だからです。
整数nが与えられたとき、開き括弧(がn個、閉じ括弧)がn個からなる整形式の文字列をすべて返してください。(が)より先になる辞書順に並べます。
関数
- ninteger
- 括弧のペアの数
- 戻り値string-array
- n組のすべての整形式文字列を辞書順に
制約
1 ≤ n ≤ 8- 答えは
n = 8のとき、1,430 個の文字列です。
例
- 入力
- n = 3
- 出力
- ["((()))", "(()())", "(())()", "()(())", "()()()"]
- 説明
- 3組のペアから、整形式の文字列が5つできます。
((()))は最初に3組すべてを開くため、最初に並びます。()()()は各ペアをすぐに閉じるため、最後に並びます。
- 入力
- n = 1
- 出力
- ["()"]
- 説明
- 1組には、整形式の文字列が1つあります。唯一の別の並び方である
)(は、何も開かれていないうちに閉じてしまいます。
発展問題
n 組の正しく構成された文字列を、生成せずに数えられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
文字列を左から右へ読み、開いているペアの数を数えます。その数がゼロ未満になる場合、何が問題なのでしょうか？
文字列を1文字ずつ作ります。
(は、それを置いた数がn未満の間追加でき、)は、置いた)の数が(の数より少ない間追加できます。この方法で作った文字列は、必ず最後まで完成させることができます。2つのカウンター、
openedとclosedを使って再帰します。(の分岐を)の分岐より先に試し、呼び出しから戻った後に各文字を削除し、長さが2nに達したら文字列を保存します。(を先に試すことで、出力がソートされた状態に保たれます。
解説
長さ 2n の文字列のうち、正しく形成されるものはごくわずかです。n = 8 の場合、65,536 個中 1,430 個です。各文字列を左から右へ作り、接頭辞をまだ完成させられる場合にのみ文字を追加します。それを判断するのは2つのカウンターで、( を ) より先に試すと、文字列はソートされた順に並びます。
すべての文字列を作成してから、確認しましょう
考え方
( と ) のあらゆる組み合わせで 2n 個の位置を埋めると、4^n 個の文字列ができるので、正しい形式のものを残します。文字列を確認するには、バランスを取りながら順に見ていきます。( では 1 を加え、) では 1 を引きます。バランスが一度も 0 未満にならず、最後に 0 になれば正しい形式です。各位置で ( を ) より先に置くと、文字列がソート順に並びます。
各文字列の確認には O(n) かかります。n = 8 の場合、答えは 1,430 個に対して文字列は 65,536 個なので、作業の約 98% が無駄になり、括弧のペアが 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開閉の数が合うように戻る
考え方
チェックを構築処理の中に移します。接頭辞が正しい形式の文字列に成長できるのは、n 個以下の ( を使い、) の数が ( の数を決して上回らない場合に限られます。したがって、opened < n の間は ( が許され、closed < opened の間は ) が許されます。長さが 2n になると、どちらの数も n となり、文字列は正しい形式になっているため、確認することは何も残っていません。
正しい形式の文字列のすべての接頭辞は、両方のルールに従うため、答えを見落とすことはありません。無駄な分岐もありません。n = 2 の場合、(( の分岐は2回閉じるしかなく、(()) となります。一方、() の分岐は開いて閉じるしかなく、()() となります。各文字列は木を通る1つの経路に対応するため、出力されるのは1回だけです。また、( の分岐が先に進むため、出力はソートされています。
すべての葉が答えとなるため、処理量は出力に比例します。O(4^n / √n)。
アルゴリズム
- 作成中の文字列と、どちらも0に設定した
openedおよびclosedの2つのカウンターを保持します。 - 文字列の長さが
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
落とし穴と境界ケース
closed < openedではなく、closed < nの間に)を許可すること。これでは())(が生成され、開かれていないかっこを閉じてしまいます。- 最後に個数が一致することだけを確認すること。これでは
)(も受け入れてしまいます。各ステップで、残高が0以上でなければなりません。 (より先に)を試すこと。正しい文字列が逆順に生成されます。- リストや文字列ビルダーがミュータブルな場合に、コピーではなく共有バッファーを保存すること。保存された答えがすべて同じバッファーを参照し、バックトラッキングによってそのバッファーが再び空になります。
- 固定サイズの結果配列を小さな予想値で確保すること。
n = 8では答えが1,430個あります。
よくある質問3
Generate Parentheses の時間計算量は何ですか？
バックトラッキングはC(n) = (2n)! / ((n+1)! n!)個の文字列を出力します。これはカタラン数で、4^n / (n^1.5 √π)のように増加します。それぞれの文字列の構築とコピーにはO(n)かかるため、時間計算量は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 のサイズについて合計すると、カタラン数の漸化式が得られます。
Generate Parenthesesは再帰を使わずに解けますか？
はい。部分状態をスタックに保持します。各状態は2つのカウンターを含む文字列で、同じ2つのルールで各状態を拡張します。(の拡張が先にポップされ、出力がソートされた状態になるように、)の拡張を(の拡張より先にプッシュします。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def generateParenthesis(n):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
n = 3
期待される出力
["((()))", "(()())", "(())()", "()(())", "()()()"]