394. Decode String

題目網址：https://leetcode.cn/problems/decode-string/

題意：給一經過編碼的 string, 返回它解碼後的 string。

編碼規則為：k[encoded_string], 表示括號中的 encoded_string 重覆 k 次, 其中 k 保證為正整數。

input string 總是有效的, 其中沒有額外的空格, 且括號總是符合格式要求的。

此外, 所有的數字都只表示重覆的次數 k, e.g. 不會出現像 3a 或 2[4] 的輸入。

Solution：

想法：利用 Stack, 可分成以下四種情況

當 s[i] 為數字時, 則不斷更新當前數字 num

當 s[i] 為字母時, 則不斷更新當前 string res

當 s[i] 為 [ 時, 則將 num、res 各自 push 到對應的 stack 中

當 s[i] 為 ] 時

取出 times = nums.top(), 並將當前 string res 累加 times 次到 strs.top() 中

再將 strs.top() assign 給 res

最後, 分別 pop nums、strs

e.g. s = "3[a2[c]]"

i = 0, s[i] = "3"：num = 3, res = ""

i = 1, s[i] = "["：nums = {3}, strs = {""}, 且 num = 0, res = ""

i = 2, s[i] = "a"：num = 0, res = "a"

i = 3, s[i] = "2"：num = 2, res = "a"

i = 4, s[i] = "["：nums = {3, 2}, strs = {"", "a"}, 且 num = 0, res = ""

i = 5, s[i] = "c"：num = 0, res = "c"

i = 6, s[i] = "]"：

num = 2, res = "c" ➔ nums = {3}, strs = {"", "acc"}
➔ strs = {""}, res = "acc"

i = 7, s[i] = "]"：

num = 3, res = "acc" ➔ nums = {}, strs = {"", "accaccacc"}
➔ strs = {""}, res = "accaccacc"

class Solution {
public:
    string decodeString(string s) {
        const int n = s.size();
        int num = 0;
        string res = "";
        stack<int> nums;
        stack<string> strs;

        for (int i = 0; i < n; ++i) {
            if (isdigit(s[i])) {
                num = num * 10 + (s[i] - '0');
            } else if (isalpha(s[i])) {
                res += s[i];
            } else if (s[i] == '[') {
                nums.emplace(num);
                strs.emplace(res);
                num = 0;
                res = "";
            } else { // 若 s[i] == ']'
                const auto times = nums.top();
                nums.pop();

                for (int k = 0; k < times; ++k) {
                    strs.top() += res;
                }

                res = strs.top();
                strs.pop();
            }
        }

        return res;
    }
};

time：$O(n)$ ➔ 遍歷 s, 其中 n 為 s 的長度
space：$O(n)$ ➔ 若不考慮 res, 則取決於 nums、strs 的長度, 而兩者的長度皆不超過 n