# LeetCode Easy 20. Valid Parentheses

tags: leetcode

問題

• Explore
• Problems

アイデア

｢文字列が与えられ､正しいカッコであるかどうかを判定せよ｣という問題です｡

正しいカッコかどうかはスタックを使えば簡単に判定することが可能です｡

解法

文字列を走査して､文字の種類に応じて処理をします｡

スタックで今まで走査した文字を管理します｡

計算量

与えられる文字列 s の長さを $N$ とします｡

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(N)$

Python

class Solution:
    def isValid(self, s: str) -> bool:
        paren_stack = []
        for paren in s:
            if paren in "({[":
                paren_stack.append(paren)
            elif not paren_stack:
                return False
            elif paren == ")" and paren_stack[-1] == "(":
                paren_stack.pop()
            elif paren == "}" and paren_stack[-1] == "{":
                paren_stack.pop()
            elif paren == "]" and paren_stack[-1] == "[":
                paren_stack.pop()
            else:
                return False
        return not paren_stack