給定一個只包含
'('、')'、'{'、'}'、'['、']'的字串s，判斷它是否為合法的括號組合。開括號必須以正確順序和對應的閉括號關閉。
Example:
Input: s = ”()[]{}” Output: true
Intuition
TIP
核心思路：遇到開括號就壓入堆疊，遇到閉括號就彈出棧頂檢查是否匹配。最後堆疊為空則合法。
- 括號匹配是「最近的開括號」配「最近的閉括號」，天然符合 LIFO 特性
- 用 Map 建立閉括號到開括號的映射，簡化匹配邏輯
- 三種不合法情況：閉括號多餘（棧空時遇到閉括號）、不匹配、開括號多餘（結束時棧非空）
Approaches
1. String Replace — O(n^2) / O(n)
- Idea: 反覆將
"()"、"[]"、"{}"替換為空字串，直到無法替換為止。若最終字串為空則合法 - Time:
O(n^2)- 每輪替換 O(n)，最多 n/2 輪 - Space:
O(n)- 字串複製
class Solution {
fun isValid(s: String): Boolean {
var str = s
while (str.contains("()") || str.contains("[]") || str.contains("{}")) {
str = str.replace("()", "").replace("[]", "").replace("{}", "")
}
return str.isEmpty()
}
}⭐ 2. Stack — O(n) / O(n)
- Idea: 遍歷字串，開括號壓入堆疊，閉括號彈出棧頂比較。不匹配或棧空提前回傳 false，結束時檢查棧是否為空
- Time:
O(n)- 每個字元處理一次 - Space:
O(n)- 最壞情況全是開括號
class Solution {
fun isValid(s: String): Boolean {
val stack = ArrayDeque<Char>()
val map = mapOf(')' to '(', ']' to '[', '}' to '{')
for (c in s) {
if (c in map) {
if (stack.isEmpty() || stack.removeLast() != map[c]) {
return false
}
} else {
stack.addLast(c)
}
}
return stack.isEmpty()
}
}WARNING
別忘了最後檢查 stack.isEmpty()——像 "(((" 這樣只有開括號的輸入，遍歷過程不會觸發 false，但結果應為 false。
🔑 Takeaways
- Pattern: 括號匹配是 Stack 最經典的應用場景
- Key trick: 用 Map 存閉括號到開括號的映射，讓匹配邏輯乾淨俐落；Kotlin 的
ArrayDeque是高效的 Stack 實作