LeetCode / Valid Parentheses

https://leetcode.com/problems/valid-parentheses/

Given a string 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.
Note that an empty string is also considered valid.

Example 1:
Input: "()"
Output: true

Example 2:
Input: "(){}"
Output: true

Example 3:
Input: "(]"
Output: false

Example 4:
Input: "([)]"
Output: false

Example 5:
Input: "{}"
Output: true

Parenthesesというのは括弧という意味らしいです。初めて知った。。。
括弧が正しい順序で閉じられているか判定する問題です。後入れ先出し（一番最後に始まった括弧をまず閉じなければならない）ですね。
小学生の頃、こんがらがった記憶があります。小学校のプログラミング教育 兼 算数教育に使えそう。

回答・解説

解法1

公式の解説はこちら。 listの変数stackにopenする括弧を格納しておき、closeする括弧が現れたら、最後にopenした括弧と対応しているかチェックします。
ほとんどの解法で、対応する括弧をハッシュテーブルに格納しておくのは共通です。

class Solution(object):
    def isValid(self, s):
        stack = []
        mapping = {")": "(", "}": "{", "]": "["}
        for char in s:
            # closeする括弧が現れたら、最後にopenした括弧をstackから取り出しtop_elementとし、closeする括弧との対応をチェック
            if char in mapping.keys():
                # stackが空、つまりopenした括弧の中でcloseされていない括弧がないときにcloseする括弧が現れたら、'#'を格納（この後すぐfalseを返す）
                top_element = stack.pop() if stack else '#'
                if mapping[char] != top_element:
                    return False
            # openする括弧が現れたら、stackに格納
            else:
                stack.append(char)
        return not stack

解法2

対応する括弧をハッシュテーブルに格納するのは同じですが、こちらはopenする括弧をkeyに、closeする括弧をvalueにとります。 計算量はさほど変わりません。

class Solution(object):
    def isValid(self, s):
        mapping = {"(": ")", "[": "]",  "{": "}"}
        open_par = set(["(", "[", "{"])
        stack = []
        for char in s:
            if char not in open_par:
                if stack and char == mapping[stack[-1]]:
                    stack.pop()
                else:
                    return False
            else:
                stack.append(char)
        return not stack