394. Decode String

Medium

Description

給定一個編碼字串 s，規則為 k[encoded_string]，表示括號內的字串重複 k 次。回傳解碼後的字串。

Example:

Input: s = “3[a2[c]]” Output: “accaccacc”

Intuition#

核心思路：用兩個堆疊分別追蹤重複次數和之前的字串，遇到 ] 時將當前字串重複後與之前的字串拼接。

巢狀結構天然適合堆疊（或遞迴）
遇到 [ 時保存當前狀態（次數和已累積的字串），遇到 ] 時恢復並組合

Approaches#

1: 遞迴#

概念: 用全域索引追蹤位置，遇到 [ 遞迴處理內部字串，遇到 ] 返回結果
時間複雜度: O(n * maxK) - n 為解碼後字串長度
空間複雜度: O(n) - 遞迴深度

class Solution {
    private var i = 0

    fun decodeString(s: String): String {
        i = 0
        return decode(s)
    }

    private fun decode(s: String): String {
        val sb = StringBuilder()

        while (i < s.length && s[i] != ']') {
            if (s[i].isDigit()) {
                var k = 0
                while (i < s.length && s[i].isDigit()) {
                    k = k * 10 + (s[i] - '0')
                    i++
                }
                i++ // 跳過 '['
                val inner = decode(s)
                i++ // 跳過 ']'
                repeat(k) { sb.append(inner) }
            } else {
                sb.append(s[i])
                i++
            }
        }

        return sb.toString()
    }
}

⭐2: 雙堆疊#

概念: countStack 存重複次數，stringStack 存 [ 之前累積的字串。遇到 [ 壓入狀態，遇到 ] 彈出並組合
時間複雜度: O(n * maxK) - n 為解碼後字串長度
空間複雜度: O(n)

class Solution {
    fun decodeString(s: String): String {
        val countStack = ArrayDeque<Int>()
        val stringStack = ArrayDeque<StringBuilder>()
        var current = StringBuilder()
        var k = 0

        for (c in s) {
            when {
                c.isDigit() -> {
                    k = k * 10 + (c - '0')
                }
                c == '[' -> {
                    countStack.addLast(k)
                    stringStack.addLast(current)
                    current = StringBuilder()
                    k = 0
                }
                c == ']' -> {
                    val count = countStack.removeLast()
                    val prev = stringStack.removeLast()
                    val repeated = current.toString().repeat(count)
                    current = prev.append(repeated)
                }
                else -> {
                    current.append(c)
                }
            }
        }

        return current.toString()
    }
}

🔑 Takeaways#

Pattern: 巢狀結構（括號配對）問題，堆疊或遞迴都可以處理
關鍵技巧: 雙堆疊分別追蹤「重複次數」和「之前累積的字串」。遇到 [ 保存狀態（push），遇到 ] 恢復狀態（pop）並組合。注意數字可能是多位數