06. Valid Parentheses

読了目安約1分

Stack / LeetCode 20 (Easy) — 括弧の並びが正しいかをスタックで判定する。

この章の目次

問題

LeetCode 20. Valid Parentheses（Easy / カテゴリ: Stack）

(、)、{、}、[、] だけからなる文字列 s が与えられます。どの開き括弧も同じ種類の閉じ括弧で、正しい順序で閉じられているとき true を返してください。 ([)] のように交差する対応は不正です。

考え方

ヒント 1

最後に開いた括弧が、最初に閉じられなければなりません。この「後入れ先出し」はスタックの性質そのものです。

ヒント 2

開き括弧はスタックに積みます。閉じ括弧が来たら、スタックの一番上が対応する開き括弧かを確かめて取り出します。最後にスタックが空なら正しい並びです。

Swift 実装のポイント

Swift にスタック型はありませんが、配列の append と popLast() がそのままスタックになります。
popLast() は空のとき nil を返すため、「空なのに閉じ括弧が来た」場合も stack.popLast() != open の 1 つの比較で弾けます。
閉じ括弧から開き括弧への対応表を [Character: Character] の辞書で持つと、分岐が減ります。

模範解答

Swift
class Solution {
    func isValid(_ s: String) -> Bool {
        let pairs: [Character: Character] = [")": "(", "]": "[", "}": "{"]
        var stack: [Character] = []
        for ch in s {
            if let open = pairs[ch] {
                if stack.popLast() != open {
                    return false
                }
            } else {
                stack.append(ch)
            }
        }
        return stack.isEmpty
    }
}

計算量: O(n) 時間、O(n) 追加メモリ。