今日題目

題目連結：20. Valid Parentheses
題目主題：String, Stack

玩了幾題排序後，接下來會分享兩種重要的資料結構Stack & Queue，今天選的題目是很典型的Stack題目。

簡單說說 Stack

Stack（堆疊）是一種後進先出 ( LIFO ) 的資料結構，新增資料永遠從後面進去，取出資料永遠從最後面資料取出，使用的方式及過程如下圖。

可以想像 Stack 是一個圓角方形空間，以圖中範例來看，如果有一個新的值進去這個空間，一定會從最後面進去放在最後一個位置。每一次取出時也是從最後面取出，不能隨便從其他位置取出。

題目解說

建議可以看看LeetCode原本的題目說明，這邊是用我的方式說明題目，參考就好。

本題的目標是確認一個字串中是否有平衡的出現 () , {} , [] 三種括號，開括號要由相同類型的括號關閉，有平衡的話就回傳 True。若出現不平衡的狀況，如 : (] , [} , {()] ,，就會回傳False。這題建議看範例比較好理解。

約束：

• 1 <= s.length <= 104
• 字串是由'() [] {}'組成的

範例1

輸入: s = "()"
輸出: true

範例2

輸入: s = "()[]{}"
輸出: true

範例3

輸入: s = "(]"
輸出: false
解釋: 以 '(' 開頭應該要由 ')' 結尾，但範例是 ']' 結尾，因此這題回false。

範例4

輸入: s = "([)]"
輸出: false
解釋: 以 '([' 開頭，後面應該要出現的關閉順序應為 '])' 才能平衡配對，但範例是 ')]'，因此這題回false。

範例5

輸入: s = "{[]}"
輸出: true
解釋: 以 '{[' 開頭，後面關閉的順序也是 ']}'，有達到平衡配對，因此這題回true。

建議到這邊先停下來，嘗試自己解解看，若沒有想法可再繼續走下去。

解題的想像

文字描述

1. 宣告一個stack
2. 跑一個迴圈每一圈檢查一個字元
   • 遇到一個開括號就放進stack中
   • 遇到一個關括號就從stack取出一筆資料檢查是否有配對成功
     • 若沒有配對成功直接回傳False結束
     • 若有配對成功繼續往下個字元檢查
3. 最終如果stack是空的，代表都有配對到是平衡的，回傳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

希望您今天能瞭解到...

1. Stack基礎概念
2. 20. Valid Parentheses 解題方法

若內容有什麼問題或建議歡迎一起交流：）
感謝您今天願意花時間看完這篇文章~~~~

Next：232. Implement Queue using Stacks