Decode String
題目描述
給定一個編碼字串，規則為 k[encoded_string]，表示 encoded_string 重複 k 次。回傳解碼後的字串。
輸入: s = "3[a2[c]]"
輸出: "accaccacc"
輸入: s = "2[abc]3[cd]ef"
輸出: "abcabccdcdcdef"
解題思路
遍歷字元
用 for 迴圈逐一掃描 s 的每個字元，根據字元類型分四種處理
遇到數字
用 num = num * 10 + digit 累積多位數字，例如遇到 1 再遇到 2 得到 12
遇到 [
把 current 字串壓入 strStack、num 壓入 numStack，然後 current 和 num 都重置為初始值
遇到 ]
從 strStack 彈出前綴 prev、從 numStack 彈出次數 repeat，組合成 prev + current × repeat
遇到字母
直接用 current += c 附加到當前字串
程式碼
C#
public class Solution {
public string DecodeString(string s) {
// Stack 儲存 (之前的字串, 重複次數)
var strStack = new Stack<string>();
var numStack = new Stack<int>();
var current = "";
int num = 0;
foreach (char c in s) {
if (char.IsDigit(c)) {
num = num * 10 + (c - '0'); // 處理多位數
} else if (c == '[') {
strStack.Push(current); // 保存前綴
numStack.Push(num); // 保存重複次數
current = "";
num = 0;
} else if (c == ']') {
var prev = strStack.Pop();
var repeat = numStack.Pop();
current = prev + string.Concat(Enumerable.Repeat(current, repeat));
} else {
current += c;
}
}
return current;
}
}TypeScript
function decodeString(s: string): string {
const strStack: string[] = [];
const numStack: number[] = [];
let current = "";
let num = 0;
for (const c of s) {
if (c >= "0" && c <= "9") {
num = num * 10 + Number(c); // 處理多位數
} else if (c === "[") {
strStack.push(current); // 保存前綴
numStack.push(num); // 保存重複次數
current = "";
num = 0;
} else if (c === "]") {
const prev = strStack.pop()!;
const repeat = numStack.pop()!;
current = prev + current.repeat(repeat);
} else {
current += c;
}
}
return current;
}Python
def decodeString(s: str) -> str:
str_stack = []
num_stack = []
current = ""
num = 0
for c in s:
if c.isdigit():
num = num * 10 + int(c) # 處理多位數
elif c == '[':
str_stack.append(current) # 保存前綴
num_stack.append(num) # 保存重複次數
current = ""
num = 0
elif c == ']':
prev = str_stack.pop()
repeat = num_stack.pop()
current = prev + current * repeat
else:
current += c
return current複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n × maxK) | O(n) |
n 是解碼後字串長度，maxK 是最大重複次數。Time 為 O(n × maxK) 是因為每個字元最多被重複 maxK 次寫入結果字串；Space 為 O(n) 是因為 Stack 深度取決於巢狀層數，最多存 n 個字元的前綴資訊。
邊界情況
- 無巢狀編碼：如
"3[a]"直接展開為"aaa"，Stack 只會壓入和彈出一次 - 純字母無編碼：如
"abc"沒有任何數字和括號，直接逐字元附加到 current 回傳 - 多位數字：如
"100[a]"需要正確累積三位數字 100，不能只讀第一位
圖解
圖表展示了 Stack 在解碼過程中的核心角色：數字和前綴字串分別壓入兩個 Stack，遇到 ] 時彈出組合。整個流程是一個「壓入-彈出-拼接」的循環，最終 current 變數累積出完整結果。
進階觀點
💡面試追問
Q: 遞迴解法和 Stack 解法有什麼差異？
A: 遞迴解法用函式呼叫堆疊隱式模擬 Stack，遇到 [ 進入遞迴、遇到 ] 返回解碼結果。兩者時間複雜度相同，但遞迴有 call stack 深度限制（巢狀層數極深時可能 stack overflow），Stack 解法更安全。遞迴寫法更直觀但需要用全域 index 追蹤掃描位置。
Q: 如果輸入可能格式不合法怎麼辦？
A: 需要加入驗證：檢查括號是否配對（Stack 最後應為空）、數字後是否一定跟著 [、] 時 Stack 是否為空。面試時先問清楚輸入是否保證合法。
變體題：LC 726 Number of Atoms（化學式解析）、LC 1190 Reverse Substrings Between Each Pair of Parentheses。
理解測驗
🤔 處理 "12[a]" 時，數字 12 要怎麼累積？
🤔 遇到 [ 時，為什麼要把當前字串壓入 Stack？