初心者から始めるプログラミング LeetCode:Valid Parentheses

はじめに

就活が始まり、コードテストなるものを受けるようになった。プログラミング自体は1~2年ほど前から学んでいたため、なんとかなるだろうとたかを括っていたら意外と難しい。しかも、今自分が使っている言語(TypeScript)はどうやらコードテストには向いていないらしい・・・
ちょうど、大学院の研究でPythonを使い始めたのでこれを機にPythonでアルゴリズムを学ぼうと決意。
その中で、自分が引っかかった点や学びになった点を備忘録を兼ねて記載していきます。

本日はLeetCodeからStackの理解におすすめと噂の20.Valid Parenthesesを解いていきます。

問題

{　,　}　,　[　,　]　,　(　,　)この6種類の文字が組み合わされて文字列sとして与えられます。
例えば、s='{]()'など
その時,Sが正しい括弧の並びになっているかを判定するというもの。
例えば、

s='()'はtrue
s='{}()[]' はtrue
s='{)[)'はfalse

空文字列もtrueになるのには要注意です。

解法

まず考えたことはペアをどう教えるかということです。
今回は辞書のkeyとvalueとして pair = {'(':')','{':'}','[':']'}と管理することにしました。

次に、正誤判定の方法に関して。ここではスタックという考え方を活用しました。

スタックのイメージはこんな感じ。ブロックが縦に積んであると一番最後に積んだものしかとれないですね。
スタックとはいくつかの要素の中で最後に追加したものを取り出すという考え方になります。

今回のケースで考えると、左側の括弧が出てきたときはそれに対応する右括弧をStackに保存します。
stack.append(pair[char])
右側の括弧が出てきた場合それが’最後に保存された’右括弧と一致するかを確認し、一致した場合Stackから除外します。仮に一致しなかった場合、その時点で括弧が成立していないことがわかります。
Array.pop()は配列から最後の要素を除外しながらその除外した要素を返してくれます。とても便利ですね。

上の操作を文字列の中の全ての文字に行いStackの長さが0(0でなかったら余っている左括弧があるので括弧として成立していません。)のときにTrueを返せば完了です！

これらを行ったのが以下のコード

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        pair = {'(':')','{':'}','[':']'}
        
        for char in s:
            if char in pair.keys():
                stack.append(pair[char])
            else:
                if len(stack) == 0 or char != stack.pop():
                    return False
        
        if len(stack) == 0:
            return True
        return False

終わりに

今回学んだことは、
・Array.pop()はただ配列から要素を消すのではなく、消した要素も受け取れる。
・要素を1列に並べ、最後に加えられた要素から取り出していくデータ構造をスタックという。
でした！

また、コーディングの勉強をするたびに時間があれば書いていこうと思うので最後まで読んでくださった方がいれば改善点など教えていただけると幸いです。