leetCodeをPythonで解いていく-20 (Valid parenthesis)

leetCodeでやった問題を、アウトプットしていきます。

Contents

前置き
問題
解法
結果
雑感

前置き

回答日: 2022.03

とりあえず、https://leetcode.com/discuss/career/449135/How-to-effectively-use-LeetCode-to-prepare-for-interviews の問題リストを解いていこうと思います。

今回は2問目。少し前に1問目のNo.13を解いて、最初はアルゴリズムの勉強をしていくと思ったばかりでした。

が、ろくに勉強も進めず2問目に突入してしまいました。

やっぱりプログラミングしているほうが面白いですしね。。。

というわけで、2問目 No.20 Valid Parenthesesです。

問題

問題	レベル	選択言語
20 Valid Parentheses	easy	Python3

内容: ()[]{}の6種類の文字を使った文字列が与えられるので、括弧の組和合わせがOKかどうかを判定しなさいという問題。

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.

Example 1:
Input: s = “()”
Output: true

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

Example 3:
Input: s = “(]”
Output: false

解法

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 != 0: return False
        lefts = []
        for v in s:
            if v in ['(', '{', '[']:
                lefts.append(v)
            else:
                if len(lefts) == 0: return False
                if f"{lefts[-1]}{v}" in ['()', '{}', '[]']:
                    lefts.pop(-1)
                else:
                    return False
        if len(lefts) > 0:
            return False
        else:
            return True
if __name__ == '__main__':
    print(Solution().isValid("()"))
    print(Solution().isValid("()[]{}"))
    print(Solution().isValid("(}"))
    print(Solution().isValid("(("))
    print(Solution().isValid("){"))