Valid Parentheses
括弧文字 (、)、[、]、{、}だけで構成された文字列 s が与えられます。括弧の対応が正しい場合は true を返します。つまり、各閉じ括弧が、まだ閉じられていない最も直近の開き括弧を閉じ、その2つが同じ種類であり、最後に開いたままの括弧が残っていない場合です。それ以外の場合は false を返します。
関数
- sstring
- 確認する括弧の文字列
- 戻り値boolean
- 括弧の対応が取れているかどうか
制約
1 ≤ s.length ≤ 104sに含まれる文字は(、)、[、]、{、}のみです。
例
- 入力
- s = "[]{}()"
- 出力
- true
- 説明
- 3組のペアが横に並び、それぞれ開いた直後に閉じます。
- 入力
- s = "{[()()]}"
- 出力
- true
- 説明
- 2 組の丸括弧は角括弧の内側で閉じ、角括弧は波括弧の内側で閉じます。すべての閉じ括弧は、まだ閉じられていない最も新しい開き括弧に対応します。
- 入力
- s = "{(})"
- 出力
- false
- 説明
}が現れた時点で、その後に開かれた(はまだ閉じられていないため、種類の異なる括弧を閉じようとしています。
発展問題
文字列に丸括弧しか含まれていない場合、スタックの代わりに単一のカウンターを使って、追加の領域を O(1) に抑えて確認できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
文字列を左から右へ読みます。閉じ括弧が現れたとき、どの開き括弧を閉じてよいでしょうか？
閉じることができるのは、最も直近に開かれ、まだ閉じられていない開始括弧だけです。最後に開いたものを最初に閉じる。これが、スタックが保持する順序です。
開き括弧が出るたびにスタックに積みます。閉じ括弧が出たとき、スタックが空でなく、頂上の括弧が同じ種類でなければなりません。それを取り出して続けます。文字列の終わりにスタックが空の場合に限り、括弧の対応が取れています。
解説
括弧の数を数えるだけでは不十分です。{(})には開き括弧と閉じ括弧がそれぞれ1つずつありますが、順序が重要なため、正しくありません。スタックを使うと、まだ閉じられていない括弧を開いた順に保持できるので、スタックを使って一度走査すれば、文字列全体を判定できます。
一致するペアを繰り返し削除する
正しいが、最大のテストでは終わらない
考え方
すべての正しい括弧列には、{[()]} の中の () のように、括弧の間に何もない最も内側の一組があります。隣り合った対応する一組を削除しても、その文字列が正しい括弧列かどうかは変わりません。したがって、1回の処理で何も削除されなくなるまで削除を繰り返します。正しい括弧列は空になり、正しくない括弧列は、最初から {(}) であるように、文字が残ったまま行き詰まります。
各回では文字列全体を走査して新しいコピーを作ります。また、(((...))) のような入れ子の文字列では、1回につき一組ずつ減ります。最大で n/2 回の処理が必要になり、各回の計算量は O(n) なので、合計では O(n²) です。
アルゴリズム
- 文字列内の
()、[]、{}をすべて削除します。 - その回で何も削除されなかった場合は、停止します。
- そうでなければ、短くなった文字列で繰り返します。
- 文字列が空になった場合は
trueを、括弧が残っている場合はfalseを返します。
def isValid(s):
while True:
# Delete every adjacent matched pair in one round.
shorter = s.replace("()", "").replace("[]", "").replace("{}", "")
if shorter == s:
break # nothing left to delete
s = shorter
return s == ""スタックを使った1回の走査
考え方
閉じ括弧は、まだ閉じられていない括弧のうち、最後に開かれたものを閉じなければなりません。最後に入ったものが最初に出るという順序は、まさにスタックが保つものです。
各開き括弧が待っている閉じ括弧をプッシュします。次に、閉じ括弧はスタックの一番上と一致しなければなりません。スタックが空なら閉じる対象がなく、一番上が異なれば別の種類の括弧を閉じようとしています。たとえば、)が一番上にあるときの{(})の}がそうです。最後に、((のようにスタックに何かが残っていれば、それは開かれたまま閉じられていません。各文字は一度だけプッシュまたはポップされます。時間計算量はO(n)で、スタック上の要素数は最大でもnです。
アルゴリズム
- 空のスタックを作成します。
- 開き括弧の場合、対応する閉じ括弧をプッシュします。
- 閉じ括弧の場合、スタックが空、またはスタックの先頭が異なる文字であれば
falseを返します。それ以外の場合はポップします。 - 最後の文字の後、スタックが空の場合にのみ
trueを返します。
def isValid(s):
closers = {'(': ')', '[': ']', '{': '}'}
stack = []
for ch in s:
if ch in closers:
stack.append(closers[ch])
elif not stack or stack.pop() != ch:
return False
return not stack
落とし穴と境界ケース
- 括弧の種類ごとに数えること。
{(})は個数が一致していますが、それでも無効であり、)(は順序だけで無効になります。 - 空のスタックから取り出すこと。
}や)]}のように閉じ括弧で始まる文字列は、クラッシュせずにfalseを返さなければなりません。 - 最後のチェックを省略すること。
(([{は不正な閉じ括弧に遭遇しないため、残ったスタックを確認しないと無効だと分かりません。 - 長さを当てにすること。奇数の長さは常に無効ですが、偶数の長さだからといって有効とは限りません。
(]と())(はどちらも無効です。 - 削除する方法で、括弧をエスケープせずに正規表現やLuaパターンに渡すこと。そこでは
(と[に意味があるため、プレーンテキストとして置換してください。
よくある質問3
Valid Parentheses の時間計算量は何ですか？
スタックを使った解法の実行時間はO(n)です。各文字は高々1回だけプッシュまたはポップされるためです。最悪の場合、開き括弧だけの文字列ではO(n)の空間を使います。一致するペアを繰り返し削除する方法はO(n²)の時間がかかります。深くネストした文字列では、1回の処理で削除されるペアが1つだけだからです。
Valid Parentheses でスタックが使われるのはなぜですか？
括弧は入れ子になるため、最後に開いた括弧を最初に閉じる必要があります。スタックを使えば、その括弧を一番上に保持でき、定数時間で読み取って取り除けるので、チェック全体を O(n) で行えます。
空文字列は有効な括弧列ですか？
はい。空文字列には対応していない括弧がないため、バランスが取れています。スタックは空のままで、削除ループで削除するものはありません。この問題では、s には常に少なくとも1文字あります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def isValid(s):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
s = "[]{}()"期待される出力
true