394. 字符串解码

难度：🟡 Medium | 标签：栈、字符串 | 状态：⬜ LeetCode 链接

思路

两个栈：数字栈 + 字符串栈。

• 数字：累加 num
• [：把 num 和当前 cur 压栈，重置
• ]：弹出旧字符串和数字 k，prev + cur * k 作为新 cur
• 字母：拼到 cur

代码

class Solution {
public:
    string decodeString(string s) {
        stack<int> numStk;
        stack<string> strStk;
        string cur;
        int num = 0;
        for (char c : s) {
            if (isdigit(c)) num = num * 10 + (c - '0');
            else if (c == '[') {
                numStk.push(num); num = 0;
                strStk.push(cur); cur.clear();
            } else if (c == ']') {
                int k = numStk.top(); numStk.pop();
                string prev = strStk.top(); strStk.pop();
                string repeated;
                repeated.reserve(prev.size() + cur.size() * k);
                repeated += prev;
                while (k--) repeated += cur;
                cur = std::move(repeated);
            } else {
                cur += c;
            }
        }
        return cur;
    }
};

复杂度

• 时间 O(n · 平均复制系数)，空间 O(n)

易错 / 回顾

• 数字可能 ≥ 10，必须累加而不是单字符
• 嵌套靠两栈联动
• 别把 cur 也当 char 单独处理