iT邦幫忙

2021 iThome 鐵人賽

DAY 3
2
自我挑戰組

【帶你輕鬆入門演算法-Leetcode】系列 第 3

【第三天 - Stack 題目分析】

先簡單回顧一下,今天預計分析的題目:

    1. Valid Parentheses
    • 題目敘述
  • 昨天問到,如果 ([)] 是錯誤的,那什麼是正確的 ?
    • 你寫 ()[] 或 [()] 或 ([]) 都可以,在你遇到右括號時,對應的左括號,都是 same type 就可以
      • 例如 ( 對 ) 就是 same type, ( 對 ] 就不是 same type
  • 小學數學運算中,{}是大括號,[]是中括號,()是小括號,優先順序為小括號 > 中括號 > 大括號,那這一個題目,遇到 ([{}]) 這樣的情況,是不是也是可接受的 ?
    • 可以的,長大後,我們已經較少使用 [] 跟 {} 做為算式的一部分,大部分數學中的運算都是全部使用 () ,然後依照最內部的括號依序做運算
    • 中括號與大括號,在數學中有其他涵義,例如大括號常做為集合,中括號可表示高斯符號
  • 根據觀察,我們是不是平常數學式中,遇到右括號,就會去找與之對應的左括號
    • 舉例括號
  • 所以程式整體邏輯很簡單:
    1. 我們一個個讀 s 中的每個字元,例如 s 為 {},那我們先讀 {,再讀 }
      • PS: 這樣 { 我們會稱為字元,超過一個字元組成,就會變成字串,例如{},會組成字串
    2. 字元遇到左括號,我們就先用 stack 盒子存起來,若字元為右括號,就把剛剛存起來的左括號拿出來比對是不是 same type
      • PS: ( 對 ) 就是 same type,( 對 ] 或 } 就不是 same type,以此類推
    3. 當每個字元都讀完,最後我們再來檢查看看 stack 是不是都空了,如果都空了,就代表他左右括號數量一樣,那就回傳 True,反之就回傳 False
      • 之所以要檢查,就是怕若 s 為 ((),那在前面兩個步驟中,stack 盒子會裝 ((,但是只遇到一次 ),只拿出一次(,所以盒子內還會有一個 (
  • 不專業程式流程圖,請依照步驟慢慢對照: (菱形為判斷式;長方形為程式一般執行,可能儲存變數等..;平行四邊形為輸入與輸出;圓角長方形代表程式的開始或結束)
    • 程式流程圖
  • 課間小Q&A:
    • 若變數 s 為 {}{}()[[]] ,stack 盒子會依序裝入哪些字元? 是否回傳 True?
      1. 曾經依序裝入 {{([[
        1. 先裝入 {,遇到 } 又把{拿出來了,所以stack 為空
        2. 再裝入 {,遇到 } 又把{拿出來了,所以stack 為空
        3. 再裝入 (,遇到 ) 又把(拿出來了,所以stack 為空
        4. 再依序裝入 [[,遇到 ] 把一個 [ 拿出來了,所以stack 裡面還有一個 [,接著又遇到 ],又把stack 內的 [ 拿出來,此時 stack 為空
      2. 因為每次遇到右括號都是 same type,加上最後 stack 是空的,代表左右括號數量一樣,所以回傳 True
  • python 一般寫法 (比較沒有彈性) ( 時間複雜度為 O(n) → 就是全部 s 長度跑一次 )
class Solution:
    def isValid(self, s: str) -> bool:
#       先宣告一個 stack 盒子,之後專門存放左括號
        stack_left = []
#       把變數 s 一個個讀字元,每一次讀的字元存在 chr 變數中
        for chr in s:
#           若 chr 為左括號
            if chr == "(" or chr == "[" or chr == "{":
                stack_left.append(chr)
#           若 chr 不是左括號  (chr 為右括號)
            else:
#               若 stack 內還有東西 (因為要拿一個 stack 盒子中的左括號,出來跟右括號比對是否為 same type)
                if stack_left:
#                   stack 盒子拿出來的左括號放在 left 變數中
                    left = stack_left.pop()
#                  接下來三個判斷式,依序判斷是否為 same type,一旦不是就直接回傳 False
                    if chr == ")" and left != "(":
                        return False
                    elif chr == "]" and left != "[":
                        return False
                    elif chr == "}" and left != "{":
                        return False
#               若都讀到右括號了,但是 stack 沒有左括號可以配對,那就直接回傳 False 
                else:
                    return False
#       判斷 stack 是否為空,stack若是空的 為 True
#       stack 內有東西
        if stack_left:
            return False
#       stack 內沒有東西了~
        else:
            return True
  • 若程式想要更有彈性,可能之後不只()[]{}這幾種符號,那我們可以把比對 same type 寫成 dictionary 的結構 ( 時間複雜度為 O(n) → 就是全部 s 長度跑一次 )
class Solution:
    def isValid(self, s: str) -> bool:
        stack_left = []
        dict = {")": "(", "]": "[", "}": "{"}
        for chr in s:
#           若 chr 為 左括號
            if chr in dict.values():
                stack_left.append(chr)
#           若 chr 為 右括號
            elif chr in dict.keys():
#               若 stack 盒子是空的、沒有對應到 same type,回傳 False
                if len(stack_left) == 0 or dict[chr] != stack_left.pop():
                    return False
            else:
                return False
            
        return not stack_left

上一篇
【第二天 - Stack 介紹】
下一篇
【第四天 - Queue 介紹】
系列文
【帶你輕鬆入門演算法-Leetcode】30

尚未有邦友留言

立即登入留言