如何用栈解码形如 3[a2[c]] 的字符串？

简化版

字符串解码遇到嵌套括号时，用两个栈分别保存进入 [ 前的重复次数和已构造字符串。遇到数字累积倍数，遇到 [ 入栈并重置当前串，遇到 ] 弹出倍数和上一层前缀，拼接 prefix + current.repeat(k)。

详细版

例如 3[a2[c]]，外层要重复 a2[c] 三次，内层 2[c] 要先解成 cc。栈的作用是保存外层上下文，等内层结束时恢复。

String decodeString(String s) {
    Deque<Integer> counts = new ArrayDeque<>();
    Deque<StringBuilder> prefixes = new ArrayDeque<>();
    StringBuilder cur = new StringBuilder();
    int num = 0;
    for (char ch : s.toCharArray()) {
        if (Character.isDigit(ch)) {
            num = num * 10 + (ch - '0');
        } else if (ch == '[') {
            counts.push(num);
            prefixes.push(cur);
            cur = new StringBuilder();
            num = 0;
        } else if (ch == ']') {
            int k = counts.pop();
            StringBuilder prev = prefixes.pop();
            prev.append(cur.toString().repeat(k));
            cur = prev;
        } else {
            cur.append(ch);
        }
    }
    return cur.toString();
}

多位数字要累积，不能只读取单个字符。嵌套层级越深，栈越能体现“先处理最里面”的顺序。

完整版教学

一、为什么这题需要栈

编码串里的 [ 和 ] 表示嵌套结构。内层没有结束前，外层的前缀和重复次数都不能丢。例如 3[a2[c]] 中，读到第二个 [ 时，外层已经知道 3[ 和前缀 a，但必须先把 2[c] 解完。

3[ a 2[ c ] ]
外层次数 3
内层次数 2
先得到 cc，再得到 acc，最后重复 3 次

栈正好保存“暂停的外层现场”，等内层结束后恢复。

二、两个栈分别保存什么

一个栈保存重复次数 counts，另一个栈保存进入括号前已经构造好的字符串 prefixes。遇到 [ 时，说明即将进入一层新的子问题，需要把当前上下文压栈；遇到 ] 时，当前子串完成，弹出上下文并拼回上一层。

栈	保存内容	何时入栈	何时出栈
`counts`	当前括号前的重复次数	遇到 `[`	遇到 `]`
`prefixes`	进入括号前的前缀	遇到 `[`	遇到 `]`

这种写法比递归更直观，也避免了手动维护递归返回位置。

三、数字为什么要累积

重复次数可能是多位数，例如 12[a]。逐字符扫描时读到 1 不能立刻确定次数，因为后面可能还有 2。所以要用 num = num * 10 + digit 累积。

读 '1': num = 1
读 '2': num = 1 * 10 + 2 = 12
读 '[': 12 入栈，num 清零

遇到 [ 后必须把 num 清零，否则下一层数字会被上一层污染。

四、手算嵌套流程

以 3[a2[c]] 为例：

字符	操作	当前串	次数栈
`3`	累积数字	""	[]
`[`	3 入栈，前缀入栈	""	[3]
`a`	加入当前串	”a”	[3]
`2[`	2 入栈，前缀 “a” 入栈	""	[2,3]
`]`	得到 “acc"	"acc”	[3]
`]`	重复 3 次	”accaccacc”	[]

栈顶总是最近一层括号，对应“最里面先结束”的规则。

五、实现细节和复杂度

Java 中 StringBuilder 适合累积字符串，避免频繁创建中间字符串。repeat(k) 的代价和输出长度成正比，所以复杂度应按解码后字符串长度 m 计算，而不是只看输入长度 n。

输入长度 = n
输出长度 = m
时间复杂度 = O(n + m)
空间复杂度 = O(嵌套深度 + m)

如果语言没有 repeat，可以用循环追加 k 次。面试时要说明输出本身就可能很大，复杂度不可能低于输出长度。

六、常见误区与追问

记忆钩子：遇到 [ 是“暂停外层，进入内层”；遇到 ] 是“内层交卷，回到外层”。

误区：只用一个字符串栈就够。 还需要保存重复次数，否则 ] 时不知道当前子串重复几次。
误区：数字只会是一位。 高频测试会给 10[a]、100[ab]，必须累积多位数。
误区：遇到 ] 后把结果直接返回。 只有最外层结束才返回；内层结束要拼回上一层继续扫描。
追问：能用递归吗？ 可以，每遇到 [ 递归解析子串，返回解码结果和新位置；本质仍是调用栈。
追问：为什么复杂度和输出长度有关？ 因为最终必须生成完整解码字符串，输出 10000 个字符至少要写 10000 次。
追问：括号不合法怎么办？ 常规算法题默认合法；工程场景要在出栈前检查空栈、结束后检查栈是否为空。

七、加强记忆

字符串解码的核心是“上下文保存”：数字栈保存重复几次，字符串栈保存外层前缀，当前串只负责正在解析的最内层。读数字累积，读 [ 入栈重置，读 ] 弹栈拼接。把这三个动作记牢，嵌套再深也只是重复同一套流程。

简化版

详细版