LeetCode解説　一日一問　20. Valid Parentheses

LeetCodeって？
問題
回答
1. 解法
コード
結果

LeetCodeって？

LeetCode - The World's Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

LeetCodeとは、アルゴリズムやデータ構造を実践を通して学べる海外のプログラミング学習サイトです。

2022年12月現在2,000問を超える問題が登録されています。

各問題では、特定の入力をしたときに特定の返り値を出力する関数を作成することを求められます。

正誤判定は自動で行われます。

使用できる言語は、C++、C#、JAVA、Python3、Go、JSなど19言語が用意されています。

私はPython3で解いています。

Pythonではじめるアルゴリズム入門伝統的なアルゴリズムで学ぶ定石と計算量 [ 増井敏克 ]

問題

Valid Parentheses - LeetCode

Can you solve this real interview question? Valid Parentheses - Given a string s containing just the characters '(', ')', '{', '}', '', determine if the input s...

タイトル：20. Valid Parentheses

難易度：Easy

内容：

３種類の括弧、()、{}、[]のみで構成された文字列 s が与えられる。

括弧の順が正しければ Ture を、正しくなければ False を返す。

例：

Input: s = "()"
Output: true

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

Input: s = "(]"
Output: false

”(()”のように括弧の数が合わなかったり、”()(]”のように括弧の種類が違う場合はFalseを返します。

回答

右括弧が出てきた場合、まだペアになっていない一番近い左括弧とペアになる必要があります。

最後に入れたものを取り出せるスタックを使って解いてみます。

解法

左括弧が出てきた場合スタックにしまっていき、右括弧が出てきた場合スタックに最後にしまわれたものとペアになるか確認します。

文字列の最後まで行ければ成立しているのでTureを返します。

以下が起きると成立していないことが分かるので False を返します。

スタックに何もないのに右括弧が出てきた
スタックから取り出したものと次の右括弧がペアにならない
スタックにまだ残っているのに s を全て確認し終えた

まず括弧の辞書を用意します。

右括弧が出てきたときに該当する左括弧はどれかを示す辞書です。

ついでにスタックを初期化します。

parentheses_dict = {')':'(', '}':'{', ']':'['} # 括弧の辞書
stack = [] # スタックを初期化

s を1文字ずつ確認していき辞書に無ければ（左括弧）スタックに詰めていきます。

辞書にあれば（右括弧）スタックから取り出した値とペアになるかを確認します。途中で１．２．の不成立事象があった場合は False を返します。

for i in range(len(s)):
    if s[i] not in parentheses_dict: # sのi文字目が辞書に無ければ（左括弧）
        stack.append(s[i]) # スタックに挿入
    else: # 辞書にあれば（右括弧）
        if len(stack) == 0: # 1.スタックに何もないのに右括弧に出てきた場合
            return False
        if parentheses_dict[s[i]] != stack[-1]: # 2.スタックから取り出したものと次の右括弧がペアにならない場合
            return False
        stack.pop(-1) # スタックから左括弧を取り出す

s の最後の文字まで確認したら３．の不成立事象を確認します。

３．も起きていなければTrueを返します。

if len(stack) > 0: # sを最後まで確認したのにスタックに何か残っている場合
    return False

コード

コード全文です。

class Solution:
    def isValid(self, s: str) -> bool:
        parentheses_dict = {')':'(', '}':'{', ']':'['}
        stack = []

        for i in range(len(s)):
            if s[i] not in parentheses_dict:
                stack.append(s[i])
            else:
                if len(stack) == 0:
                    return False
                if parentheses_dict[s[i]] != stack[-1]:
                    return False
                stack.pop(-1)
        if len(stack) > 0:
            return False
        return True

計算量はO(N)です。

コードはgithubにも保管しています。