iT邦幫忙

2021 iThome 鐵人賽

DAY 5
1
Software Development

我在刷LeetCode時邂逅了Python系列 第 5

Day 5:20. Valid Parentheses

今日題目

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

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


簡單說說 Stack

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

https://ithelp.ithome.com.tw/upload/images/20210919/20141336lfAYfRyVCE.png

可以想像 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 = "{[]}"

https://ithelp.ithome.com.tw/upload/images/20210919/20141336xmZCL7uTQS.png

可以把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


上一篇
Day 4:88. Merge Sorted Array
下一篇
Day 6:232. Implement Queue using Stacks
系列文
我在刷LeetCode時邂逅了Python30

尚未有邦友留言

立即登入留言