[Leetcode] 20. Valid Parentheses

2023/11/29閱讀時間約 3 分鐘

題目 : 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:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.


Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false


  1. Michelle小梦想家參考解答

lookup : 建立(){}[]符號的字典

stack : 將讀進來的左括號暫存在這邊,用堆疊的方式存取

item : 目前讀到s的字元

line 8 : 如果讀取到的字元是lookup中的Key

line 9 : 用append()將item堆疊至stack容器中

line 10 : 如果這時候的stack沒有任何字元,代表沒有可以對應的左括號 -> False

用pop()方法將stack的最後一個字元讀取出來,並移除列表中的最後一個元素

如果最後一個元素在lookup中所對應的右括號和item不相同 -> False

line 12 : 如果直接回傳True可能會判斷錯誤,ex : s="["

所以要在最後return的時候判斷stack是否是清空的狀態

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

lookup = {"(":")","{":"}","[":"]"}
stack = []

for item in s:
if item in lookup: # ({[
stack.append(item)
elif len(stack)==0 or lookup[stack.pop()] != item: # )}]
return False
return len(stack)==0 # s="["



7會員
36內容數
這裡會放一些我寫過的 Leetcode 解題和學習新技術的筆記
留言0
查看全部
發表第一個留言支持創作者!