ゼロから始めるLeetCode Day12「20. Valid Parentheses」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインでだそうです。

その対策としてLeetCodeなるサイトで対策を行うようです。

※LeetCodeとは
本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトです。

せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていきます。

LeetCode

問題

20. Valid Parentheses

文字列が与えられたときに、それが「有効な括弧の並び」になっているかどうかを判定する問題。
具体的には、以下の3つのルールをすべて満たしている場合に、その文字列は有効とみなされる。

• 同じ種類の括弧で閉じる
• 正しい順序で閉じる
• 対応する開き括弧が存在する

Example 1:
Input: s = "()"
Output: true

Example 2:
Input: s = "()[]{}"
Output: true

Example 3:
Input: s = "(]"
Output: false

Example 4:
Input: s = "([])"
Output: true

Constraints:
1 <= s.length <= $10^4$
s consists of parentheses only '()[]{}'.

解法

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping = {")": "(", "}": "{", "]": "["}

        for char in s:
            if char in "([{":
                stack.append(char)
            elif char in ")]}":
                if not stack or stack[-1] != mapping[char]:
                    return False
                stack.pop()
            else:
                continue

        return not stack

開き括弧を一時保管する場所を用意する

stack = []:
開き括弧を一時的に保存するためのリスト。
開き括弧(、{、[を保存。

mapping = {")": "(", "}": "{", "]": "["}:
閉じ括弧に対応する開き括弧をマッピングするための辞書です。
これにより、閉じ括弧が検出されたときに、どの開き括弧とペアになるべきかを確認できる。

文字列を順番に見て、括弧の種類に応じて処理する

if char in "([{":
stack.append(char)
開き括弧(、{、[を見つけた場合、それをstackに追加する

elif char in ")]}":
if not stack or stack[-1] != mapping[char]:
return False
stack.pop()
閉じ括弧)、}、]を見つけた場合
stackの一番後ろにある開き括弧が、現在の閉じ括弧とペアになるべき種類のものか比較する。
もし種類が違っていたら、閉じ方の順序が間違っているので、Falseを返す。

条件を満たしていれば、スタックの一番上にある開き括弧を取り除く。
「この開き括弧は正しく閉じられたよ」という処理。

例

Input: s = "([])"

処理する文字 char	スタックの状態	処理の詳細
(	[	開き括弧。スタックに ( を追加する。
[	[(	開き括弧。スタックに [ を追加する。 (現在のスタックは (, [ の順で、[ が一番上)
]	[
)	[]	閉じ括弧。スタックは空ではなく、一番上の要素 ( は ) に対応している。スタックから ( を取り除く。

条件を満たしているので、最終的にTrueが返る。