Study

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

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

前置き

回答日: 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("){"))

結果

とりあえず思いついたのが、配列を順に見ていって、左括弧なら別配列で記憶しておく。右括弧がでてきたら、別配列の末indexと合わせて組み合わせが問題ないかを判定。これを最後までやっていくという方法でした。

ただ、問題の条件に、1 <= s.length <= 10**4 とあったので、この方法だとたぶんタイムアウトになるんだろうなと思って、とりあえず実行してみました。

そしたらPASSしちゃいました・・・・

雑感

いいんでしょうか? こんなので。

たぶん違いますね。将来、課金したときに正当を確認したいと思います。