題目連結:20. Valid Parentheses
題目主題:String, Stack
玩了幾題排序後,接下來會分享兩種重要的資料結構Stack & Queue,今天選的題目是很典型的Stack題目。
Stack(堆疊)是一種後進先出 ( LIFO ) 的資料結構,新增資料永遠從後面進去,取出資料永遠從最後面資料取出,使用的方式及過程如下圖。
可以想像 Stack 是一個圓角方形空間,以圖中範例來看,如果有一個新的值進去這個空間,一定會從最後面進去放在最後一個位置。每一次取出時也是從最後面取出,不能隨便從其他位置取出。
建議可以看看LeetCode原本的題目說明,這邊是用我的方式說明題目,參考就好。
本題的目標是確認一個字串中是否有平衡的出現 () , {} , [] 三種括號,開括號要由相同類型的括號關閉,有平衡的話就回傳 True。若出現不平衡的狀況,如 : (] , [} , {()] ,,就會回傳False。這題建議看範例比較好理解。
約束:
範例1
輸入: s = "()"
輸出: true
範例2
輸入: s = "()[]{}"
輸出: true
範例3
輸入: s = "(]"
輸出: false
解釋: 以 '(' 開頭應該要由 ')' 結尾,但範例是 ']' 結尾,因此這題回false。
範例4
輸入: s = "([)]"
輸出: false
解釋: 以 '([' 開頭,後面應該要出現的關閉順序應為 '])' 才能平衡配對,但範例是 ')]',因此這題回false。
範例5
輸入: s = "{[]}"
輸出: true
解釋: 以 '{[' 開頭,後面關閉的順序也是 ']}',有達到平衡配對,因此這題回true。
建議到這邊先停下來,嘗試自己解解看,若沒有想法可再繼續走下去。
範例: s = "{[]}"
可以把s想像成圖中最上方的陣列,每一圈取一個字元來處理。先看第一圈我們取到 '{' 因為是開括號,直接放到stack中。再來直接看到第三圈取到了關括號 ']',需要從stack取得最後進去的開括號來做配對,有成功配對成'[]',繼續處理。最後這個範例因為能清空stack,因此輸出為True。
若因為沒想法而走到這邊,建議看完想像以後再給自己一次機會試一次。
class Solution:
def isValid(self, s: str) -> bool:
stack = []
for c in s:
# 遇到開括號,將值放入stack中。
if c == '{' or c == '[' or c == '(':
stack.append(c)
# 遇到關括號,跟stack確認是否有配對到。
else:
if not stack: return False
open = stack.pop()
if c == '}' and open == '{': continue
elif c == ')' and open == '(': continue
elif c == ']' and open == '[': continue
else: return False
return not stack
若內容有什麼問題或建議歡迎一起交流:)
感謝您今天願意花時間看完這篇文章~~~~
Next:232. Implement Queue using Stacks