20. Valid Parentheses

文字列 s が '(', ')', '{', '}', '[', ']' だけで構成されている場合、その文字列が有効かどうかを判定してください。

有効な文字列の条件は以下の通り。

開き括弧は同じ種類の閉じ括弧で閉じられなければならない。
開き括弧は正しい順序で閉じられなければならない。
各閉じ括弧には対応する開き括弧が必要である。
例 1
入力: s = "()"
出力: true

例 2
入力: s = "()[]{}"
出力: true

例 3
入力: s = "(]"
出力: false

例 4
入力: s = "([])"
出力: true

class Solution {

    /**
     * @param String $s
     * @return Boolean
     */
    function isValid($s) {
        
        $map = [
            ')' => '(',
            '}' => '{',
            ']' => '[',
        ];
        $stack = [];

        for($i = 0; $i < strlen($s); $i++) {

            $char = $s[$i];

            if(isset($map[$char])) {
                if(empty($stack) || array_pop($stack) != $map[$char]) {
                    return false;
                } 
            } else {
                    $stack[] = $char;
            }
        }

        return empty($stack);
    }
}

1.連想配列で対応関係を管理
各閉じ括弧に対応する開き括弧を定義します。

2.スタックを使用
開き括弧が出てきたらスタックにプッシュ。
閉じ括弧が出てきたらスタックからポップして対応する開き括弧と一致するかをチェック。

3.最終チェック
最後にスタックが空なら全て正しく対応しているので True。
そうでなければ未対応の開き括弧が残っているため False。