題目出處

20. Valid Parentheses

難度

easy

題目分類

String, Stack

個人範例程式碼

我們先宣告一個字典，我們可以藉由字典查出對應的括弧。

class Solution:
    def isValid(self, s: str) -> bool:
        checkdict = {
            "(":")",
            "[":"]",
            "{":"}",

        }
        stack = [] # append <-> pop(-1) #FILO Last out!!!
        for ele in s:
            if ele in checkdict.keys():
                stack.append(checkdict[ele])
            elif not len(stack)<mark>0 and stack.pop(-1) </mark> ele:
                pass
            else:
                return False

        return len(stack)==0

Time Complexity

O(n)

Space Complexity

O(1)

算法說明

這題是非常經典的 Stack 考題

注意了：請務必自己想清楚為什麼是 Stack 而不是 Queue，以確保觀念清楚

基本上我們就用一個 list 來當作 Stack 儲存，
python 裡面，撇除直接使用 package，
我們可以使用 append 與 pop 的組合，用 list 拼湊出 Queue 與 Stack

• 可參考：【Python】python list 清除, 移除內容元素 remove, pop, del, clear相關用法整理 sample code (內含範例程式碼)

用 List 拼出 Queue

Queue 可以由 list append + pop(0) 組合而成

先進先出，所以我們先拿第 0 個。

用 List 拼出 Stack

Stack 可由 list append + pop(-1) 組合而成

或是也可以用 pop()，但個人不會這樣使用的原因是因為覺得 pop(-1) 對於觀念感覺會更清楚
因為 -1 也可以說明我們是拿最後一個，先進會後出

corner case 特殊情況處理

注意：就算符合中間「運算時」的規則，結束時也必須為空

Boundary conditions/ Edge conditions 邊際情況處理

x

Reference

• Simple Python solution with stack