394. Decode String

📘 題目敘述

給你一個編碼過的字串 s，請回傳它解碼後的字串。

編碼規則為：k[encoded_string] 其中 encoded_string 會被重複 k 次後接在一起，且 k 保證是正整數。

你可以假設輸入一定合法：不會有多餘空白、括號一定配對正確。

另外原始資料不包含任何數字，數字只會用來表示重複次數 k（例如不會出現 3a 或 2[4]）。

測資保證：解碼後的輸出長度不會超過 10^5。

條件限制

1 <= s.length <= 30
s 只包含小寫英文字母、數字、以及中括號 '[]'
s 保證是合法輸入
s 中所有整數都在範圍 [1, 300]

🧠 解題思路

我用「遞迴 + 游標 pos」來解析字串。

用成員變數 as 存整個字串，pos 表示目前解析到的位置。
rep(pos) 的工作：從目前 pos 開始，解析並回傳「這一層括號內（或整段）」解碼結果，直到遇到 ] 才停。

解析規則：

如果遇到字母：直接加到目前答案字串 r。
如果遇到數字：把完整數字讀成 k（可能多位數）。
讀完 k 後一定會遇到 [：
- 先跳過 [，遞迴解出裡面那段字串 in
- 回來後跳過 ]
- 把 in 重複 k 次接回 r

這樣一層一層拆開，外層會接著從正確的 pos 繼續往後解析。

所有變數

as：把輸入字串 s 存起來，讓遞迴不用一直傳整條字串
pos：目前解析到 as 的位置（游標）
r：rep 這一層正在累積的解碼結果
k：這次 k[...] 的重複次數（讀取連續數字組成）
in：遞迴解出 [...] 內部的解碼字串

🪜 主要流程步驟

1. 初始化並從頭開始解析

在 decodeString(s)：
- as = s
- 呼叫 rep(pos)，從 pos = 0 開始解碼

2. `rep(pos)`：一路解析到遇到 `]` 才結束

只要 pos 沒超出字串，且 as[pos] != ']' 就繼續：
- 如果是字母 → 加進 r，pos++
- 如果是數字 → 進入下一步解析 k[...]

3. 解析 `k[...]`：讀數字、遞迴括號內容、再重複拼接

讀出完整的 k（處理多位數）
跳過 '['
in = rep(pos) 解出括號內字串
回來後跳過 ']'
把 in 重複 k 次接到 r

4. 回傳本層結果

當遇到 ]（或字串結束）就回傳 r
pos 會停在 ] 上，交給外層去把 ] 吃掉並繼續

💻 程式碼實作

class Solution {
public:
    string as;
    int pos = 0;

    string rep(int& pos) {
        string r = "";
        int k = 0;
        while (pos < as.size() && as[pos] != ']') {
            if (as[pos] >= 'a' && as[pos] <= 'z') {
                r.push_back(as[pos]);
                pos++;
            } else if (isdigit(as[pos])) {
                k = 0;
                while (pos < (int)as.size() && isdigit(as[pos])) {
                    k = k * 10 + (as[pos] - '0');
                    pos++;
                }
                pos++; // as[pos] == '['
                string in = rep(pos);
                pos++; // as[pos] == ']'
                for (int i = 0; i < k; i++) {
                    r += in;
                }
            }
        }
        return r;
    }

    string decodeString(string s) {
        as = s;
        return rep(pos);
    }
};

🔗 題目連結

https://leetcode.com/problems/decode-string/