Leetcode [20. Valid Parentheses]

有沒有遇過修了三天三夜的 bug，居然是少了一個括號 ! 無論是程式錯誤或是版面一直不對，幸好現在的IDE都能安裝強大的擴充套件…

20. Valid Parentheses
💚 Easy
Topics: String Stack

解題思路

s = "({}])"

i = 0，stack = ['(']
i = 1，stack = ['(', '{']
i = 2 碰到 } 的時候，從 stack 檢查：

從 stack 的尾巴找到 } -> ✅ ，移除尾巴元素 }，但表有成對

i = 3 碰到 ] 的時候，從 stack 檢查：

從 stack = ['('] 的尾巴找不到] -> ❌

---

解題步驟

遍歷陣列：

• 當遇到左括號時，將符號 append 到 Stack
• 當遇到右括號時，stack 尾巴是否存在對應的左括號
  • 存在：將左括號 pop 出來
  • 不存在：返回 False
• 檢查 stack 若為空陣列，返回 True ; 反之為 False

複雜度

• 時間複雜度: O(N)
• 空間複雜度: O(N)

解題程式碼

def isValid(s):
  brackets ={"}":"{", "]":"[",")":"("}
  stacks=[]
  for char in s:
    if char in brackets.values():
      stacks.append(char)
    elif char in brackets:
      if stacks and brackets[char] == stacks[-1]:
        stacks.pop()
      else:
        return False
  return len(stacks)==0

---

VS studio 乾貨分享：

• Prettier - 自動整理程式碼格式，支援 JavaScript, CSS and JSON。

• Ruff - 由 Rust 實作的 Python Linter, 號稱速度快上其他常見的 Linter 約 10 ~ 100 倍之間。