394. Decode String

──────────────────────────────────────────────────────────────────────

394. Decode String

把 3[a2[c]] 這種編碼展開成 accaccacc。括號可以巢狀。

思路

這題跟 Calculator 題組是同一個骨架，只是運算元和運算換了：

	Calculator	394
累積中的運算元	`num`（數字）	`chars`（字串）
遇到左括號	遞迴進子問題	存檔，答案歸零
遇到右括號	結算並回傳	`前面的答案 + 次數 × 當前答案`
誰決定運算	`sign`	`[` 前面那個數字

認出這件事之後，剩下的就是把「存什麼、什麼時候取回來」想清楚。

流程是這樣：

遇到連續的字元，就把字元不斷組合起來
遇到連續的數字，就把數字不斷組合起來（12[a] 的 12 是兩個字元）
遇到 [ 時，把「（目前為止的答案，剛讀完的數字）」存進 stack —— 因為括號可能有很多層，最先遇到的要最後處理，這正是 stack 的語意。存完之後把兩者歸零，開始處理子問題
遇到 ] 時，把 stack 最上面那一組取出來，它是進括號之前的完整答案。當前答案的組法是：

新的答案 = 括號外已經有的答案 + 括號前的數字 × 括號內的答案

關鍵在第 3 步：[ 是「存檔」的時機，不是開始計算的時機。這也是這題跟 Calculator 最大的差別 —— Calculator 是遇到運算符才結算，這題是遇到右括號才結算，因為重複次數在括號前面就已經知道了。

解題方向

迭代：把外層狀態存進 stack

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        digits = 0
        chars = ''
        for char in s:
            if char == '[':
                stack.append((chars, digits))
                chars = ''
                digits = 0
            elif char == ']':
                prevChars, prevDigits = stack.pop()
                chars = prevChars + prevDigits * chars
            elif char.isdigit():
                digits = digits * 10 + int(char)
            else:
                chars += char
        return chars

存進 stack 的是一個 tuple，因為出括號時需要兩樣東西：外層累積到一半的字串，以及這一層要重複幾次。少存任何一個都拼不回來。

chars 在遇到 [ 之後歸零，所以它永遠代表「當前這一層括號內累積到的結果」；prevChars + prevDigits * chars 就是把它接回外層。

遞迴：讓呼叫堆疊幫你存

class Solution:
    def decodeString(self, s: str) -> str:
        index = 0
        def helper():
            nonlocal index
            res = ''
            while index < len(s) and s[index] != ']':
                if not s[index].isdigit():
                    res += s[index]
                    index += 1
                else:
                    digit = ''
                    while index < len(s) and s[index].isdigit():
                        digit += s[index]
                        index += 1
                    digit = int(digit)
                    index += 1
                    decodedString = helper()
                    index += 1
                    if digit > 0:
                        res = res + digit * decodedString
                        digit = 0
            return res
        return helper()

跟 224 一樣的手法：括號內是一個獨立的子問題，遞迴回傳一個字串，對外就只是一段普通的字元。

兩個 index += 1 分別是在跳過 [ 和 ]，位置不能記錯。index 用 nonlocal 共用，作用跟 224 用 deque 從左邊消耗是一樣的 —— 每一層都在同一份字串上往前推進，不會倒退。

兩種寫法的差別只有一件事：狀態存在哪裡。 迭代版自己開一個 stack 明確地存 (chars, digits)；遞迴版把它交給呼叫堆疊，res 和 digit 是每一層的區域變數，自然就分開了。224 和 772 我寫的是遞迴版，那兩題也一樣可以改寫成迭代版。

補充

if digit > 0 這個保護在題目的限制下永遠成立 —— LeetCode 保證重複次數是正整數，不會出現 0[abc]。留著沒有壞處，但它下面那行 digit = 0 是多餘的：digit 在每一輪迴圈開頭都會被重新賦值成 ''。

題組關係：

題目	括號裡是什麼	結算的觸發點
227	沒有括號	運算符 / 字串結尾
224	一個子運算式	運算符 / `(` / `)` / 結尾
772	一個子運算式	運算符 / `)` / 結尾
394	一段要重複的字串	`]`

更多 → #Stack

複雜度

時間 $O (m)$ — 其中 $m$ 是輸出的長度。輸入只掃一次是 $O (n)$ ，但 prevChars + prevDigits * chars 這種字串拼接會真的複製字元，總複製量由展開後的長度決定
空間 $O (m)$ — 輸出本身；stack 或遞迴深度是 $O (n)$ ，被 $O (m)$ 蓋過去

$n$ 是輸入長度、 $m$ 是輸出長度。3[a2[c]] 這種巢狀會讓 $m$ 隨層數指數成長（每層乘上一個倍數），所以用輸出長度來算才誠實。