394. 字串解碼

思路

跟上個題目類似，括號內的字元會被複製，次數取決於前面的數字。比如3[a]就是"aaa"。
同樣可以嵌套，也就是括號中有括號。

在沒有括號的情況下，就只要單純的讀過去取字元。
加入了括號與數字之後，遇到數字時額外紀錄次數，以供後續複製用。
除此之外的每一個步驟都跟上一個題目非常相似。

• 遇到左括號時，後續的處理用遞迴求解。
• 遞迴呼叫不清楚最後右括號的邊界，因此用全域變數where去紀錄最後處理到的位置。

程式碼

遞迴

class Solution {
public:
    string dupe(string& s, int copyTime) {
        string res;
        for(int i = 0; i < copyTime; ++i) {
            res += s;
        }
        return res;
    }
    string decodeString(string s) {
        int where = 0;
        auto dfs = [&](this auto&&dfs, int i) -> string {
            string cur;
            int copyTime = 0;
            while(i < s.length() && s[i] != ']') {
                if(isdigit(s[i])) {
                    copyTime = copyTime * 10 + (s[i++] - '0');
                }
                else if(isalpha(s[i])) {
                    cur += s[i++];
                }
                else { // 左括號
                    // dfs(i + 1) 處理括號內的字串, 最後 where 會停在右括號
                    // 將括號內的數字複製 copyTime 遍。
                    cur += dupe(dfs(i + 1), copyTime); 
                    i = where + 1; // 更新當前處理倒的位置
                    copyTime = 0;
                }
            }
            where = i; // 當前位置在尾端，或是 ]
            return cur;
        };
        return dfs(0);
    }
};

複雜度分析

• 時間複雜度：$O(n\times{k})$
• 空間複雜度：$O(n\times{k})$