見出し画像

ほぼ日刊競プロ leetcode 20. Valid Parentheses

20. Valid Parentheses

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.

考えたこと

正直自力では解けなかった.ダメだったコード↓

class Solution:
   def isValid(self, s: str) -> bool:
       for i in range(len(s)-1):
           print (s[i])
           #print (s[i+1::])
           ans = False
           if s[i]=="(" and (s[i+1]!="]" or s[i+1]!="}") and ")" in s[i+1::]:
               print (1)
               ans = True
           elif s[i]=="[" and (s[i+1]!=")" or s[i+1]!="}") and "]" in s[i+1::]:
               print (2)
               ans = True
           elif s[i]=="{" and (s[i+1]!=")" or s[i+1]!="]") and "}" in s[i+1::]:
               print (3)
               ans = True
           if s[i]=="(" and (s[i+1]=="]" or s[i+1]=="}"):
               print (4)
               ans = False
           elif s[i]=="[" and (s[i+1]==")" or s[i+1]=="}"):
               print (5)
               ans = False
           elif s[i]=="{" and (s[i+1]=="]" or s[i+1]==")"):
               print (6)
               ans = False
               
       return ans

上記では"{[]}"のようなものをFalseとしてしまう.

参考にしたコード

文字列を1つずつ見ていき,(,[,{であればstackに詰めていく.),],}であった場合は正しく閉じられているかを確認するため最後にスタックした(,[,{を見て正しい組み合わせであるかを確認する.違う組み合わせ ex:(]の時はFalseを返す.最後まで行ってstackの中身がなくなっていれば正解とする.

class Solution:
   def isValid(self, s: str) -> bool:
       stack =[]
       dict ={")":"(","}":"{","]":"["}
       for i in s:
           #if i is ( or[ , { ,pushes to stack.
           if i in dict.values():
               stack.append(i)
           #if i is ) or ] , },checks the stack whether ( or {,[.
           elif i in dict.keys():
               if stack==[] or dict[i]!=stack.pop():
                   return False
       # if stack is empty,returns True
       if stack==[]:
           return True

この記事が気に入ったらサポートをしてみませんか?