【LeetCode】20. Valid Parenthesesを解く

問題へのリンク

問題概要

'('，')'，'{'，'}'，'['，']'のみを含む文字列sが与えられる．
このとき，文字列sが「有効」であるか判定せよ．ここで「有効」であるとは，

• 括弧が同じタイプの括弧で閉じていること
• 括弧が正しい順序で閉じていること

の2つの条件を満たすものをいう．

例：

Input: s = "()[]{}"
Output: true

Input: s = "([)]"
Output: false

制約

• $1 \leq s.length \leq 10^4$

考えたこと

以下のように，与えられた入力に対して，内側から順にペアとなる括弧を除去していくことを考える：

{ { ( { } ) } }
      |_|

{ { (      ) } }
    |______|

{ {          } }
  |__________|

{                }
|________________|

この操作を行い，全ての括弧が消えた場合はTrue，ペアが見つからなかったり括弧が余ったりするとFalseを返せば良い．

しかし，問題が与えられたとき，最も内側にある括弧のペアを特定することは難しい．また，1つ目の例題s = "()[]{}"のように各括弧のペアが他の括弧に内包されているとは限らない．

従って別の手法を考える必要がある．

本記事では，スタックを用いた判定手法を紹介する．以下，(のように先に記述される括弧を「括弧開き」，)のように後に記述される括弧を「括弧閉じ」と表記する．

本手法では，「括弧閉じ」が出たとき直前の括弧が同じタイプの「括弧開き」があるかどうかを判定し，同じタイプであった場合はそのペアを消去していくという戦略をとる．

( ) [ ] { }
↑

( ) [ ] { }
  ↑

( ) [ ] { }
|_|

    [ ] { }
    ↑

    [ ] { }
      ↑

    [ ] { }
    |_| 

        { }
        ↑ 

        { }
          ↑ 

        { }
        |_|

この手法であれば，例1のような問題にも対応できるようになる．

上記のアルゴリズムは以下のように実装できる：

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        dict = {')': '(', ']':'[', '}': '{'}
        stack = []
        
        for c in s:
            if c in dict.values():
                stack.append(c)
            elif stack != [] and dict[c] == stack[-1]:
                stack.pop()
            else:
                return False
        
        return stack == []

スタックへの追加やpop操作は$O(1)$，sの走査は$O(n)$で実行できるため全体の計算量は$O(n)$となる．

最後に

この記事はLeetCodeのTop 100 Liked Questionsを順に解くというシリーズのうちの一つです．

難易度Easyから順に解説記事を書いていますが，本記事でEasy問題を全て解き終えました！

次回からは難易度Mideumを順に解いていきます．お楽しみに！