iT邦幫忙

2025 iThome 鐵人賽

DAY 26
0
自我挑戰組

從零開始學習LeetCode系列 第 26

Day 26 Valid Parentheses

  • 分享至 

  • xImage
  •  

題目:給定一個只包含 '('、')'、'{'、'}'、'['、']' 的字串,
判斷這個字串中的括號是否「成對且順序正確」
有效例子:

  • "()" → True
  • "()[]{}" → True
  • "{[]}" → True

無效例子:

  • "(]"
  • "([)]"
  • "("
    https://ithelp.ithome.com.tw/upload/images/20251010/20169339V5yEFwMBqr.jpg

解法一
https://ithelp.ithome.com.tw/upload/images/20251010/20169339p6s4ZeiABK.jpg

  • 建立一個堆疊(stack),用來存放尚未匹配的左括號
  • 遍歷字串:
    (1)若遇到左括號 '('、'{'、'[' → 推入堆疊。
    (2)若遇到右括號 → 檢查堆疊頂端是否是對應的左括號:
    (3)是 → 彈出(配對成功)
    (4)否 → 立即返回 False
  • 遍歷結束後,若堆疊為空 → 代表全部配對完成 → 回傳 True
  • 若堆疊中還有東西 → 有多餘的左括號 → 回傳 False

註解

  • stack = []:用來暫存未配對的左括號
  • mapping:定義右括號對應的左括號關係
  • stack.append(char):遇到左括號就先存起來
  • stack[-1]:取堆疊頂端元素,不移除
  • stack.pop():彈出頂端元素,代表成功配對
  • return not stack:堆疊為空代表配對完成

理解

  • 想像你在檢查一串「開口與關口」:
    (1)左括號 = 開一個門
    (2)右括號 = 關一個門
  • 要確保:
    (1)每扇門都被關上。
    (2)關門的順序要對(後開的門要先關)

上一篇
Day 25 Merge Sorted Array
下一篇
Day 27 Longest Common Prefix
系列文
從零開始學習LeetCode27
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言