【LeetCode】就活に向けたコーディングテスト対策 #06

はじめに

こんばんは．
M1就活生がLeetCodeから，easy問題を中心にPythonを用いて解いていきます．

↓では，解いた問題のまとめを随時更新しています．
まとめ記事

問題

今回解いたのは，難易度easyから 問題20のValid Parentheses です．
問題としては，括弧文字からなる入力文字列sが与えられたとき，開いた括弧が同じ種類の括弧かつ，正しい順序で閉じられているかどうか判定するというもの．

入力例と出力例は以下の通りです．

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

Input: s = "{[]}"
Output: true

書いたコード

とりあえず，思いついたままに書いてみました．

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

        for parenthesis in s:
            if parenthesis in left_parenthesis:
                stack.append(parenthesis_map[parenthesis])
            elif parenthesis in right_parenthesis:
                if parenthesis != stack.pop():
                    return False
        return True

入力文字列sから，1文字ずつ見ていき，開き括弧であれば，それに対応する閉じ括弧をstackの末尾に追加，閉じ括弧であれば，stackの末尾から取り出します．閉じ括弧の場合に，取り出したもの（開き括弧に対応する閉じ括弧）が，異なればFalseを返すことで，有効な括弧の判定を実装しました．最後まで走査できれば，有効な括弧ということでTrueを返します．

今回書いたコードでは，用意したリストが，辞書の内容と重複しています．辞書だけを利用してうまく書き直せないか調べたところ，keys()とvalues()というメソッドが有効そうであったのでこちらで書き直しました．

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

        for parenthesis in s:
            if parenthesis in parenthesis_map.keys():
                stack.append(parenthesis_map[parenthesis])
            elif parenthesis in parenthesis_map.values():
                if parenthesis != stack.pop():
                    return False
        return True

おわりに

簡単な問題でも，普段使わないものを使うことができるので，様々な知見が増えて楽しいです．
変数名や，コミットメッセージなどの決定に少し時間を掛けてしまったので，ルールを決めて効率化を図りたいものです．余談ですが，自分はオンラインゲームなどで始める名前を決めるのに時間が掛かるタイプです．皆さんはいかがでしょうか？

今回書いたコードはGitHubにもあげておきます．

前回　次回