首頁LeetCode 筆記

# 題目

輸入一個只包含 ()[]{} 的字串，判斷它是否為「有效括號」。

input string 只有在以上狀況才視為 valid:

  1. 每個開括號都有對應的閉括號，且順序正確。
  2. 開括號與閉括號的類型必須相同。

Example:

s = "()"        # True
s = "()[]{}"    # True
s = "(]"        # False
s = "([)]"      # False
s = "{[]}"      # True

# Stack

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

        for c in s:
            if c in close_bracket_key_hashmap:  # 如果 c 在 closeToOpen 中，代表他就是 closing bracket，如果不在就先存到 stack，等之後可能遇到的右括號來配對
                if stack and stack[-1] == close_bracket_key_hashmap[c]:  # 如果 stack 內有東西，且 stack 最後一個元素是對應的 open bracket
                    stack.pop()  # 如果是對的就把 stack 最後一個元素 pop 掉，
                else:
                    return False  # 如果第一個就是 closing bracket } 那就不用比了，因為順序一定錯誤，直接 return false
            else:
                stack.append(c)  # (，if c in closeToOpen: 不成立，把 ( append 到 stack 內，那如果一開始遇到 closing bracket } 那就不用比了，因為順序一定錯誤
                # print(stack)  # ['(', '[', '{']
        return True if not stack else False  # 如果 stack 內沒有東西，代表全部都配對成功，回傳 True，否則回傳 False

大概的具體執行流程，用 pseudo code 解釋，以 input ([]) 為例：


# 第一個 c '(' 不在 close_bracket_key_hashmap 中，代表是 opening bracket，就直接把他 append 到 stack 中
if c in close_bracket_key_hashmap:
    ...

else:
  stack.append()
  
# 此時的 stack = [ '(' ]

# 再來第二個 c '[' 也不在 close_bracket_key_hashmap 中，代表是 opening bracket，就直接把他 append 到 stack 中
# 此時的 stack = [ '(', '[' ]

# 再來第三個 c ')' 在 close_bracket_key_hashmap 中，代表是 closing bracket，接下來要檢查 stack 最後一個元素是否是對應的 opening bracket

# 如果 stack 不是空的，且最後一個 append 進 stack 的元素 [ == 對應的元素 [ 的話
if stack and stack[-1] == close_bracket_key_hashmap[c]:
    stack.pop()  # 就把最後一個元素 pop 掉
else:
    return False  # 如果不是對應的元素，就直接 return False

# 此時的 stack = [ '(' ]
...

# 重複以上流程，直到 s 的所有元素都被處理完

時間與空間複雜度：

  • TC：O(n)
  • SC：O(n)

# Brute Force

class Solution:
    def isValid(self, s: str) -> bool:
        # Brute Force 判斷 s 是否為空字串
        while "()" in s or "[]" in s or "{}" in s:
            s = s.replace("()", "").replace("[]", "").replace("{}", "")  # 刪除所有配對的括號
        return s == ""

時間與空間複雜度：

  • TC：O(n^2)
  • SC：O(n)