---
title: "394. Decode String"
url: "https://laigary.com/interview/coding/394-decode-string"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-27"
tags: ["String", "Stack", "Recursion"]
---

# 394. Decode String

[394. Decode String](https://leetcode.com/problems/decode-string/)

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

## 思路

這題跟 [Calculator 題組](/interview/coding/227-basic-calculator-ii)是**同一個骨架**，只是運算元和運算換了：

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

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

流程是這樣：

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

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

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

## 解題方向

### 迭代：把外層狀態存進 stack

```python
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` 就是把它接回外層。

### 遞迴：讓呼叫堆疊幫你存

```python
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](/interview/coding/224-basic-calculator) 一樣的手法：括號內是一個獨立的子問題，遞迴回傳一個字串，對外就只是一段普通的字元。

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

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

## 補充

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

**題組關係**：

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

更多 → [#Stack](/interview/coding?tag=Stack)

## 複雜度

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

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