題目描述:給定只含括號字元的字串,判斷括號是否有效(每個開括號有對應的關括號,且順序正確)。
解題思路:用堆疊:遇到開括號就推入;遇到關括號則檢查堆疊頂端是否為對應的開括號,若不匹配或堆疊為空則無效。遍歷結束後若堆疊為空則有效(所有開括號都已匹配)。
時間複雜度:O(n) — 每個字元恰好推入和彈出各一次。
空間複雜度:O(n) — 堆疊最大深度等於字串長度(全是開括號的情況)。
1. Initialize empty stack
2. For each char c in s:
a. If c is opening bracket: push c
b. Else (closing bracket):
- If stack empty: return false
- If top doesn't match: return false
- Pop from stack
3. Return stack.empty()遞迴移除:重複尋找並移除 (), [], {} 直至無法移除 — 簡單但低效。
字符配對陣列:用陣列索引而非雜湊表以加速查詢 — 時間複雜度相同但常數更優。