LeetCode 20. Valid Parentheses (Python3)

はじめに

LeetCode 「20. Valid Parentheses」の問題をPython3で解きました。

問題

https://leetcode.com/problems/valid-parentheses/description/

問題文

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:
1.Open brackets must be closed by the same type of brackets.
2.Open brackets must be closed in the correct order.
3.Every close bracket has a corresponding open bracket of the same type.

和訳
文字 '(', ')', '{', '}', '[', ']' を含む文字列 s が与えられたとき、その入力文字列が有効かどうかを判定する。

入力文字列が有効であるのは、以下の場合である：
1.開き括弧は、同じ種類の括弧で閉じなければならない。
2.開き括弧は正しい順序で閉じなければならない。
3.どの閉じ括弧にも、対応する同じ型の開き括弧がある。

例

Input: s = "()"

Output: true

Input: s = "()[]{}"

Output: true

Input: s = "(]"

Output: false

Input: s = "([])"

Output: true

制約

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

解答

この問題で、括弧が正しい順序で閉じられているかを判定するには、最後に開いた括弧が最初に閉じられる必要があります。
これは LIFO（Last-In-First-Out） の構造である スタック（Stack） を用いるのが有効です。

class Solution:
    def isValid(self, s: str) -> bool:
        stack = collections.deque([])
        pairs = { "(": ")", "{": "}", "[": "]" }
        for ch in s:
            if ch in pairs:
                stack.append(ch)
            elif len(stack) == 0 or pairs[stack.pop()] != ch:
                    return False
        return len(stack) == 0

ここではスタック用途を明示するために collections.dequeを使っていますが、listでも十分です。

stack = []

pairs は辞書型で開き括弧と閉じ括弧の対応を定義しています。
引数の文字列の各文字を走査しながら以下の流れで判定をしています。

1. 開き括弧ならスタックに push
2. 閉じ括弧ならスタックのトップと比較
   • スタックが空なら不正
   • トップと対応していなければ不正
   • 対応していれば pop
3. 最後にスタックが空なら True

計算量

• 時間的計算量：O(n)
  • 各文字を一度だけ処理する
• 空間的計算量：O(n)
  • スタックに最大n個の括弧が積まれる