(ブログ記事からの転載)
[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