LeetCode 1000000本ノック【20. Valid Parentheses】

目次

No.	項目
1	概要
2	問題
3	解法
4	メイキング

概要

●発端
　・競プロ初心者、コーディング面接でズタボロにされ、
　・最低限のアルゴリズム学習とコーディング力強化を習慣化するため記事化
●環境
　・LeetCodeブラウザ上で実装（vscodeに拡張機能にするかもシレナイ）
　・言語はpython3
●その他ルール
　・google検索は自由に（直接的なLeetCodeの問題解説ページはNG）
　　（60分実装して実装出来なければ解説ページ参照）
　・コーディング面接対策のために解きたいLeetCode 60問から問題選出
　・「1000000」は任意の2進数とする

問題

• 20. Valid Parentheses

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

⇨英語が全く読めなくても何となく雰囲気で分かりそうだが...「渡されたString引数の
　括弧が、開いた順に閉じられているか確認しろ」と書いてます。知らんけど。

念の為仕様を整理↓
　・一文字ずつ順番に確認していって...
　　・対応した開括弧と閉括弧が順序通り存在すること
　　　※　(　{　[　は連続してOKだが先に対応した　)　}　]　が存在すること

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

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

解法

実施時間：40分

特に参考記事は無し。
stackの概念があれば問題なく解けると思われますがちょっと時間かかりました。

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        brackets = {')': '(', '}': '{', ']': '['}
        for c in s:
            if c in brackets.keys():
                if len(stack) == 0:
                    return False
                if brackets[c] == stack[-1]:
                    del stack[-1]
                else:
                    return False
            if c in brackets.values():
                stack.append(c)             
        if len(stack) == 0:
            return True

メイキング

step1.コメントで仮コーディング

　class Solution:
    def isValid(self, s: str) -> bool:
            #最初がopen or closeでない
            #最後がclose or ({[でない
        #(のあとは　)　間空可
        #{のあとは　}  間空可
        #[のあとは　]  間空可
        
        #対応括弧のMAP key OPEN : value CLOSE

        #文字列をcharループ
            #openならスタックに積む
                #continue
            #closeなら
                #スタックの最新openに対応したcloseか確認
                #対応括弧で無いならFalse
        #ループ終了(全部流れきったら)でTrue

上部に実装仕様をまとめた内容をメモ。（インデントは実装の優先順位）

step2.ひとまず仕様メモの下３つ（対応括弧の確認）だけ実装します。

class Solution:
    def isValid(self, s: str) -> bool:
        #最初がopen or closeでない
        #最後がclose or ({[でない
        #(のあとは　)　間空可
        #{のあとは　}  間空可
        #[のあとは　]  間空可 
        #スタック
        stack = []
        #map　key CLOSE : value OPEN
        brackets = {')': '(', '}': '{', ']': '['}
        #文字列をcharループ
        for c in s:
            #closeなら
            if c in brackets.keys():
                #スタックの最新openに対応したcloseか確認
                if brackets[c] == stack[-1]:
                    #スタックの最後を削除して次文字へ
                    del stack[-1]
                #対応括弧で無いならFalse
                else:
                    return False
            #openならスタックに積む
            if c in brackets.values():
                stack.append(c)             
        #ループ終了したらTrue
        return True

ここでif openとif closeの順番を入れ替えてみる。
※「LOOP抜ければTrue」は変えられないので可読性的に上部にFalseまとめてみた

step3.残りの仕様実装（括弧が閉じられてる？閉じ括弧で始まってない？）

class Solution:
    def isValid(self, s: str) -> bool:
        #最初がopen or closeでない
        #最後がclose or ({[でない
        #(のあとは　)　間空可
        #{のあとは　}  間空可
        #[のあとは　]  間空可 
        #スタック
        stack = []
        #map　key CLOSE : value OPEN
        brackets = {')': '(', '}': '{', ']': '['}
        #文字列をcharループ
        for c in s:
            #closeなら
            if c in brackets.keys():
                #open無いのにclose
                if len(stack) == 0:
                    return False
                #スタックの最新openに対応したcloseか確認
                if brackets[c] == stack[-1]:
                    #スタックの最後を削除して次文字へ
                    del stack[-1]
                #対応括弧で無いならFalse
                else:
                    return False
            #openならスタックに積む
            if c in brackets.values():
                stack.append(c)             
        #ループ終了後、stack残ってなかったらTrue
        if len(stack) == 0:
            return True

後は余計なコメントを消して完了！

〜蛇足〜
記事をまとめていてelifにすべき箇所があるのに気づいたので変えてみた。
意外とパフォーマンスに影響出るもんですねぇ。
そしてテストケースは通過しているけども、「引数無しの場合」と
「引数が括弧以外」を処理し忘れているますね...精進精進......

↓

↓