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

概要

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

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

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

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day57 「35. Search Insert Position」
次回
ゼロから始めるLeetCode Day59 「1221. Split a String in Balanced Strings」

Twitterやってます。

問題

20. Valid Parentheses
難易度はEasy。

問題としては文字 ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ および ‘]’ だけを含む文字列sが与えられた場合、入力された文字列が有効かどうかを判断します。

入力文字列は、以下のような場合に有効です。

開いているカッコは、同じ種類のカッコで閉じなければなりません。
カッコは正しい順序で閉じなければなりません。
空の文字列も有効とみなされることに注意してください。

Input: “()”
Output: true

Input: “()[]{}”
Output: true

Input: “(]”
Output: false

Input: “([)]”
Output: false

Input: “{[]}”
Output: true

解法

例を見ればわかりますが、括弧の中で別に括弧が完結すればTrueになり得ますが、そうでない場合ならばFalseになる、といった風になります。

始まりと終わりをきっちり確認できれば良い、ということはスタックを使うと管理しやすいかなと思います。

例えば、Input: "{[]}"の場合で考えてみましょう。
for文を使ってcharへとsを代入し、前から読み取っていきます。
すると読み込まれる文字の順は'{','[',']','}'となります。

それをif文できちんと括弧が正しい順番で閉じられているかをチェックしなければなりません。

そのために、チェックするための括弧の集合を自前で用意してあげる必要があります。

ここではリストか辞書で管理するのが一般的かなと思います。

仮に括弧の要素をリストで管理した場合だと

open_str = ["[","{","("] close_str = ["]","}",")"]

こんな感じになり、
辞書で管理するなら
dict = {")":"(","]":"[","}":"{"}

こういった感じになるでしょう。
今回僕は辞書の方を使いました。

さて、ここまでくればあとはfor文で回した際にdictの中にchar要素が存在した場合、存在しなかった場合の処理を書けばよくなります。
仮に要素がdict.valuesの中に存在したときはどうすれば良いでしょう。
その場合は用意したstackへと追加してあげると良いでしょう。

stackの性質は皆さんご存知の通りLIFO(Last in first out)ですから、最後から取り出していくスタックは今回のようなケースの場合、都合が良いのです。

では、次にcharがdict.keysに存在する場合、そして最後にそれ以外の場合はどういった処理を行えば良いのか、ということになります。

その場合は新たに以下のような処理で書きました。

if stack == [] or dict[char] != stack.pop():
    return False

こうした場合、この内のどちらかに該当した場合False
を返します。
逆に言えば、これに該当しなければ処理は続きます。

そして、今まで書いたどの条件にも一致しない場合もFalseを返します。

これらをまとめて書いた内容が以下のようになります。

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        dict = {")":"(","]":"[","}":"{"}
        for char in s:
            if char in dict.values():
                stack.append(char)
            elif char in dict.keys():
                if stack == [] or dict[char] != stack.pop():
                    return False
            else:
                return False
        return stack == []
# Runtime: 36 ms, faster than 30.47% of Python3 online submissions for Valid Parentheses.
# Memory Usage: 13.8 MB, less than 77.84% of Python3 online submissions for Valid Parentheses.

思ったより解法パートが長くなってしまいました・・・
もっとスパッと書いた方が読む側としては楽かもしれませんね。色々読み手の側も考えながら書いていきたいと思います。

話変わりますが最近アルゴリズムやデータ構造に限らずCSについて学んでいるのですが興味があるジャンルについて勉強するのは楽しいですね！

では今回はここまで。
お疲れ様でした。