解題說明
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[...]格式?