解題說明
Decode String
題目描述：給定編碼字串如 3[a2[c]]，按規則解碼：k[encoded] 表示將 encoded 重複 k 次。括號可以嵌套。
解題思路：使用兩個 Stack：countStack 存每層的重複次數，strStack 存每層進入括號前累積的字串。掃描時遇到數字累計 k，遇到 [ 壓入當前狀態，遇到 ] 彈出狀態並將當前字串重複 k 次後拼接，遇到字母直接追加。此法自然處理任意深度的嵌套。
C++ 解法
複雜度分析
時間複雜度：O(maxK^depth × n) — 最壞情況下嵌套展開使字串指數增長，n 為輸入長度，maxK 為最大重複次數，depth 為嵌套深度。
空間複雜度：O(depth) — Stack 深度等於括號最大嵌套層數。
虛擬碼
1. Initialize countStack, strStack, current="", k=0 2. For each character c in s: a. If c is digit: k = k*10 + digit(c) b. If c == '[': push k to countStack, push current to strStack, reset k=0, current="" c. If c == ']': repeat = pop countStack, prev = pop strStack, current = prev + current*repeat d. Else: current += c 3. Return current
其他解法
遞迴（DFS）：用一個全域索引掃描字串，遇到 [ 遞迴處理內層，遇到 ] 返回。邏輯與 Stack 等價但更直觀，缺點是深度嵌套時有函式呼叫開銷。
正則展開：反覆用正規表達式匹配最內層 k[...] 並展開替換，直到不含括號。實作簡單但時間效率差，不建議用於競賽。
延伸思考
- 若重複次數可能高達 10^9，字串展開會 OOM，應如何改用惰性求值或計數方式回答查詢？
- 如何修改解法以支援負數索引（即反向重複）？
- 給定解碼後的字串，如何反向編碼成最短的
k[...]格式？