【LeetCode】20. Valid Parentheses 解答・解説【Python】

問題
1. 原文
2. 内容
方針
解答
1. 解答1
補足・参考・感想

問題

原文

Given a string s 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.

Every close bracket has a corresponding open bracket of the same type.

内容

以下の括弧を含む文字列型変数sが与えられる。入力された文字列が正しいか判断してください。

'(', ')', '{', '}', '[' and ']'

入力される文字列は以下の条件を満たせば正しいと判断できます。

開始カッコは同じ種類の終了カッコでなければならない
開始カッコはただしい順序で閉じられなければならない
全ての終了カッコは同じ種類の開始カッコでなければならない

※正しくない可能性があります。

方針

・変数s内の文字列を全探索

・開始カッコならスタックに入れる

・スタック内に文字列がない、または終了カッコだった場合は以下に分岐

→stackの要素が1つ以上あり、さらに文字列がスタックの最後(一番上)の要素と対応するカッコの場合はスタックの最後の要素を取り出す。そうでなければFalseを返す

・変数s内の文字列の探索が終了後、スタックに要素が残っていればFalse、残っていなければTrueを返す

解答

解答1

#クラス名を定義
class Solution:
  #関数を定義
  def isValid(self, s: str) -> bool:
    #開始カッコに対応する終了カッコの辞書を用意
    open_to_close = {
      '(' : ')',
      '{' : '}',
      '[' : ']'
    }
    #開始カッコをset型で用意
    open_set = set(['(', '{', '['])
　　#スタックを用意
    stack = []
　　#s内の全ての文字列に対して処理
    for charac in s:
　　　#文字列がopen_setにある場合
      if charac in open_set: # if the character is an open bracket
　　　　#stackに追加
        stack.append(charac)
　　　#文字列がopen_setにない場合(終了カッコやスタックに値がない場合)
      else: # if its the closed bracket and stack is non-empty
　　　　#かつ、stackの要素数が1以上かつstackの最後(右端)の文字列をキーとしたopen_to_closeの値と文字列が一致している場合
        if len(stack) and open_to_close[stack[-1]] == charac:
　　　　　 #stack内の最後(右端)の文字列を取得
          stack.pop()
　　　　#stackの要素数が1またはstackの最後の文字列をキーとしたopen_to_closeの値が文字列と不一致なら
        else:
　　　　　 #Falseを返す
          return False
　　#stackの要素数が1以上なら(終了カッコがない状態なら)
    if len(stack): # once we exhaust all the characs in string, then check for length of the stack
　　　#Falseを返す
      return False
　　#stack内の文字列を全てpopできたらTrueを返す
    return True

#クラス名を定義

class Solution:

#関数を定義

def isValid(self, s: str) -> bool:

#開始カッコに対応する終了カッコの辞書を用意

open_to_close = {

'(' : ')',

'{' : '}',

'[' : ']'

}

#開始カッコをset型で用意

open_set = set(['(', '{', '['])

　　#スタックを用意

stack = []

　　#s内の全ての文字列に対して処理

for charac in s:

　　　#文字列がopen_setにある場合

if charac in open_set: # if the character is an open bracket

　　　　#stackに追加

stack.append(charac)

　　　#文字列がopen_setにない場合(終了カッコやスタックに値がない場合)

else: # if its the closed bracket and stack is non-empty

　　　　#かつ、stackの要素数が1以上かつstackの最後(右端)の文字列をキーとしたopen_to_closeの値と文字列が一致している場合

if len(stack) and open_to_close[stack[-1]] == charac:

　　　　　 #stack内の最後(右端)の文字列を取得

stack.pop()

　　　　#stackの要素数が1またはstackの最後の文字列をキーとしたopen_to_closeの値が文字列と不一致なら

else:

　　　　　 #Falseを返す

return False

　　#stackの要素数が1以上なら(終了カッコがない状態なら)

if len(stack): # once we exhaust all the characs in string, then check for length of the stack

　　　#Falseを返す

return False

　　#stack内の文字列を全てpopできたらTrueを返す

return True

補足・参考・感想

スタックを使う問題のようでした。実際の面接では英語で行うことに加えて、これ以外の解法がないか、別解と今回の解法のメリットとデメリットを比較して相談しながら解法を決めた上でミスなく早くコーディングを行うことが求められるのだろうなと思います。

スタックを書いてみたのは初めてだったので、一般的に今回のような書き方をするのか、他にも何か決まった書き方のようなものがあるのか、勉強してみたいと思います。