LoginSignup
0

More than 3 years have passed since last update.

LeetCode / Valid Parentheses

Posted at

ブログ記事からの転載)

[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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0