LeetCodeって？
LeetCodeとは、アルゴリズムやデータ構造を実践を通して学べる海外のプログラミング学習サイトです。
2022年12月現在2,000問を超える問題が登録されています。
各問題では、特定の入力をしたときに特定の返り値を出力する関数を作成することを求められます。
正誤判定は自動で行われます。
使用できる言語は、C++、C#、JAVA、Python3、Go、JSなど19言語が用意されています。
私はPython3で解いています。
Pythonではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量 [ 増井 敏克 ]
問題
タイトル：22. Generate Parentheses
難易度：Medium
内容：
自然数 n が与えられる (1 <= n <= 8)。
n 個の括弧 () がとりうるすべてのパターンを返す。
例：
Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]
Input: n = 1 Output: ["()"]
“())(” や ” ))(( ” など括弧として成り立っていない場合や、同じパターンを出力してはいけません。
回答
再起関数を使って、全ての組み合わせを網羅する方法を考えてみます。
解法
返り値を入れるリストを初期化します。
ans = []残りの左括弧の数を l 、右括弧の数を r 、現在できている文字列を cand として、括弧の文字列パターンを生成する再起関数 generater を考えます。
def generater(cand, l, r):
初期値では cand = “”, l = r = n となります。
まず l == 0 の場合、つまり左括弧を使い切った場合を考えます。
l == 0 かつ r == 0 の場合、文字列の生成が終わっているので ans に cand を詰めます。
また l == 0 かつ r > 0 の場合、右括弧がまだ残っているので、 cand に右括弧を足したものと、右括弧を消費するので r から1引いたものを引数として 再度 generater に渡します。
if l == 0:
if r == 0:
ans.append(cand)
else:
generater(cand + ")", l, r - 1)
次に、 l == r の場合、つまり左右の括弧の残数が同じ場合を考えます。
文字列を左から見ていったときに、左括弧よりも多く右括弧が出てくることはできません。なので l == r になったということは次は必ず左括弧になります。
elif l == r:
generater(cand + "(", l - 1, r)初期値では必ずこの条件分岐に入ります。
それ以外、つまり左括弧が残っていて右括弧よりも多い場合を考えます。
この場合、左括弧も右括弧もどちらもとれるので、どちらのパターンも作ります。
else:
generater(cand + "(", l - 1, r)
generater(cand + ")", l, r - 1) この条件分岐で generater を2回呼んでいることで、すべてのパターンを網羅することができます。
コード
コード全文です。
class Solution:
def generateParenthesis(self, n):
ans = []
def generater(cand, l, r):
if l == 0:
if r == 0:
ans.append(cand)
else:
generater(cand + ")", l, r - 1)
elif l == r:
generater(cand + "(", l - 1, r)
else:
generater(cand + "(", l - 1, r)
generater(cand + ")", l, r - 1)
return ans
return generater("", n, n)コードはgithubにも保管しています。
n = 2 の場合の解説
再起関数は直感で分かりにくいので n = 2 の場合を説明します。
１．初期値は l == r == 2 なので2つ目の条件分岐に入り、次の引数で generater が呼ばれます。
generater("(", 1, 2)２-１．次は3つ目の条件分岐に入り、左括弧を追加した generater が呼ばれます。
generater("((", 0, 2)３-１．l == 0、r != 0となるので1つ目の条件分岐に入り、右括弧が足される工程が2回あります。
generater("(()", 0, 1)
generater("(())", 0, 0)４-１．l == r == 0 となったので、ans に”(())”を詰めます。
２-２．ここで、２．に戻り今度は右括弧を追加した generater が呼ばれます。
generater("()", 1, 1)３-２．l == r == 1 となったので2つ目の条件分岐に入り、左括弧が追加されます。
generater("()(", 0, 1)４-２． l == 0 なので、1つ目の条件分岐で右括弧を追加します。
generater("()()", 0, 0)l == r == 0 となったので、ans に”()()”を詰めます。
以上で、n = 2 の全パターン “(())” , “()()” が ans に入りましたので、ans を返して終了です。
結果
まずまずの結果でした。
再起関数って頭がこんがらがりますよね。
コメント