20. Valid Parentheses

Easy
Description

給定一個只包含 '('、')'、'{'、'}'、'['、']' 的字串 s，判斷它是否為合法的括號組合。開括號必須以正確順序和對應的閉括號關閉。

Example:

Input: s = “()[]{}” Output: true

Intuition#

核心思路：遇到開括號就壓入堆疊，遇到閉括號就彈出棧頂檢查是否匹配。最後堆疊為空則合法。

  • 括號匹配是「最近的開括號」配「最近的閉括號」，天然符合 LIFO 特性
  • 用 Map 建立閉括號到開括號的映射，簡化匹配邏輯
  • 三種不合法情況：閉括號多餘（棧空時遇到閉括號）、不匹配、開括號多餘（結束時棧非空）

Approaches#

1: 字串替換（Replace）#

  • 概念: 反覆將 "()"、"[]"、"{}" 替換為空字串，直到無法替換為止。若最終字串為空則合法
  • 時間複雜度: O(n^2) - 每輪替換 O(n)，最多 n/2 輪
  • 空間複雜度: 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#

  • 概念: 遍歷字串，開括號壓入堆疊，閉括號彈出棧頂比較。不匹配或棧空提前回傳 false，結束時檢查棧是否為空
  • 時間複雜度: O(n) - 每個字元處理一次
  • 空間複雜度: 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()
    }
}

別忘了最後檢查 stack.isEmpty()——像 "(((" 這樣只有開括號的輸入，遍歷過程不會觸發 false，但結果應為 false。

🔑 Takeaways#

  • Pattern: 括號匹配是 Stack 最經典的應用場景
  • 關鍵技巧: 用 Map 存閉括號到開括號的映射，讓匹配邏輯乾淨俐落；Kotlin 的 ArrayDeque 是高效的 Stack 實作
Backward Stack 22. Generate Parentheses Forward