字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为：k[encoded_string]，表示方括号内部的 encoded_string 恰好重复 k 次。k 保证为正整数。

可以认为输入字符串总是有效，输入字符串中没有额外空格，且方括号总是符合格式要求。

原始数据不包含数字，所有数字只表示重复次数 k，例如不会出现 3a 或 2[4] 这样的输入。

测试用例保证输出字符串的长度不会超过 10^5。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

提示：

• 1 <= s.length <= 30
• s 由小写英文字母、数字和方括号 '[]' 组成
• s 保证是一个有效的输入
• s 中所有整数的取值范围为 [1, 300]

栈：

class Solution {
public:
    string decodeString(string s) {
        stack<int> countStk;
        stack<string> stringStk;
        string current;
        int count = 0;

        for (char c : s)
        {
            if (isdigit(c))
            {
                count = count * 10 + (c - '0');
            }
            else if (c == '[')
            {
                countStk.push(count);
                stringStk.push(current);
                count = 0;
                current.clear();
            }
            else if (c == ']')
            {
                int repeat = countStk.top();
                countStk.pop();

                string previous = stringStk.top();
                stringStk.pop();

                string decoded;
                for (int i = 0; i < repeat; ++i)
                {
                    decoded += current;
                }

                current = previous + decoded;
            }
            else
            {
                current += c;
            }
        }

        return current;
    }
};

核心思想

这题的难点在于方括号可以嵌套。

遇到 [ 时，当前正在构造的字符串需要暂时保存起来，等内部字符串解码完成后，再把它接回来。

遇到 ] 时，说明当前这一层编码结束，需要取出这一层对应的重复次数，把当前字符串重复后接到进入这一层之前的字符串后面。

这正好符合栈的“后进先出”特点：

最后遇到的左方括号，必须最先遇到对应的右方括号并完成解码。

因此使用两个栈：

• countStk：保存每一层方括号对应的重复次数
• stringStk：保存进入这一层方括号之前已经构造好的字符串

再使用两个变量：

• count：当前正在读取的数字
• current：当前这一层正在构造的字符串

栈中存什么

countStk

countStk 中保存每一层 [ 对应的重复次数。

例如扫描到：

3[a2[c]]

扫描到内层 [ 时，栈中会保存：

[3, 2]

栈顶 2 对应最内层的 2[c]，应该优先处理。

stringStk

stringStk 中保存进入当前方括号之前的字符串。

例如扫描到：

ab3[cd]

遇到 [ 时，当前已经构造出字符串 ab，因此把 ab 压入 stringStk。

等 cd 重复三次得到 cdcdcd 后，再恢复之前的字符串：

ab + cdcdcd

结果就是 ab cdcdcd。

字符扫描逻辑

遇到数字

数字可能不止一位，所以不能只保存当前字符。

读取数字时使用：

count = count * 10 + (c - '0')

例如读取字符 12 的过程是：

• 先读到 1，count = 1
• 再读到 2，count = 1 * 10 + 2 = 12

遇到 [

当前的 count 和 current 都属于即将进入的新一层编码。

因此先保存它们：

countStk.push(count);
stringStk.push(current);

然后开始处理方括号内部内容：

count = 0;
current.clear();

遇到字母

字母属于当前层的字符串，直接追加到 current：

current += c;

遇到 ]

当前层字符串已经读取完成。

先从 countStk 取出重复次数，从 stringStk 取出进入当前层之前的字符串。

然后将当前字符串重复 repeat 次：

for (int i = 0; i < repeat; ++i)
{
    decoded += current;
}

最后接回上一层：

current = previous + decoded

这样当前层就被完整解码，并重新成为上一层的一部分。

为什么遇到 ] 时可以直接结算

输入保证方括号格式有效。

因此遇到 ] 时，当前 current 一定正好对应最近一个还没有闭合的 [。

由于栈顶保存的就是最近进入的那一层，所以：

• countStk.top() 是当前层的重复次数
• stringStk.top() 是当前层开始前的字符串

把当前层结算后弹出这两个栈顶元素，就回到了外层的处理状态。

这也是嵌套编码能够被正确处理的原因。

边界情况

如果字符串只包含普通字母，例如：

s = "abc"

所有字符都会直接追加到 current，最后返回 abc。

如果同一层有多个编码片段，例如：

s = "2[abc]3[cd]ef"

第一个 ] 处理完成 2[abc]，第二个 ] 再处理 3[cd]，最后把 ef 追加到结果末尾。

如果编码存在多层嵌套，例如：

s = "3[a2[c]]"

内层 2[c] 会先解码成 cc，再和外层的 a 拼成 acc，最后整体重复三次。

数字可能有多位，例如 12[a]，代码通过累加方式正确得到重复次数 12。

题目保证输入有效，因此不需要额外处理缺少右括号、重复次数缺失等非法情况。

正确性证明

我们证明：算法返回的字符串正好是输入编码字符串的解码结果。

结论 1：current 始终表示当前层已经读取内容的解码结果

当扫描到普通字母时，字母本身就是当前层解码结果的一部分，算法把它追加到 current 中。

当扫描到 [ 时，算法把当前层已有字符串保存到 stringStk，并清空 current，开始单独处理新的一层。

当扫描到 ] 时，当前 current 已经包含这一层方括号内部字符串的解码结果。算法取出对应的重复次数，将 current 重复后接到进入这一层之前的字符串后面。

因此，每处理完一个字符或一个完整编码片段，current 都准确表示当前层已处理内容的解码结果。

结论 2：两个栈顶始终对应同一层方括号

每遇到一个 [，算法同时向 countStk 和 stringStk 各压入一个元素。

其中：

• countStk 保存这一层的重复次数
• stringStk 保存进入这一层之前的字符串

每遇到一个 ]，算法同时弹出两个栈的栈顶元素。

由于输入中的方括号嵌套关系符合格式要求，最后进入的方括号一定最先结束。

所以两个栈的栈顶始终对应当前正在结束的那一层方括号。

结论 3：每个方括号片段都会被正确重复

考虑任意一个完整片段：

k[encoded_string]

扫描到 [ 时，算法保存重复次数 k 和进入该片段前的字符串。

在遇到对应的 ] 之前，算法会完整处理 encoded_string，包括其中可能存在的嵌套片段。

由结论 1 可知，遇到 ] 时，current 正好是 encoded_string 解码后的结果。

算法将它重复 k 次，得到：

encoded_string 的解码结果重复 k 次

这正是编码规则要求的结果。

结论 4：算法不会遗漏或重复普通字符

算法从左到右扫描输入字符串中的每个字符。

普通字母只会在扫描到它时追加一次。

数字只用于组成重复次数，不会被加入结果。

方括号只用于控制嵌套范围，也不会被加入结果。

每个编码片段只会在遇到对应的 ] 时结算一次。

所以所有普通字符都会按照原有顺序出现，且不会被额外添加或遗漏。

得出结论

由结论 1 可知，current 始终正确表示当前层的解码结果。

由结论 2 可知，每次结算都会取到正确层级的重复次数和前置字符串。

由结论 3 可知，每个编码片段都按照规则被正确重复。

由结论 4 可知，普通字符不会被遗漏或重复处理。

因此算法返回的字符串正好是输入字符串解码后的结果。

举例理解

以：

s = "3[a2[c]]"

为例。

扫描过程如下：

最终返回：

"accaccacc"

复杂度分析

设最终解码结果的长度为 L，输入字符串长度为 n。

扫描输入字符串需要 O(n) 时间。

此外，算法需要把最终结果中的每个字符写入字符串，因此总时间复杂度为：

O(n + L)

题目保证 L <= 10^5，所以该复杂度可以满足要求。

两个栈保存嵌套层级信息，最多有 O(n) 个元素；current 和最终构造的字符串需要 O(L) 空间。

所以空间复杂度是：

`O(n + L)