#394. 字符串解码

• LeetCode：394. 字符串解码
• 难度：中等
• 归类：栈、递归、字符串
• 主解法：栈保存外层上下文

#先给结论

遇到 k[encodedString] 时，不能在读到 [ 后丢掉方括号外已经解码的内容。栈中需要为每个尚未闭合的 [ 保存两项信息：

• 进入当前括号前已经解码的前缀。
• 当前括号内容需要重复的次数。

扫描到 ] 时，当前层内容已经完整，将栈顶上下文弹出并合并：

当前结果 = 外层前缀 + 当前层结果重复 k 次

多位重复次数要逐位累积，不能把 12[a] 当成 1[a] 或 2[a]。

#题目描述

给定一个经过编码的字符串 s，返回它解码后的字符串。编码规则为：

k[encodedString]

表示把方括号内的 encodedString 恰好重复 k 次。编码可以嵌套。

示例 1：

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

示例 2：

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

示例 3：

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

题目保证：

• 1 <= s.length <= 30。
• s 只包含小写英文字母、数字和方括号。
• 输入一定有效，方括号正确匹配且没有多余空格。
• 数字只表示重复次数，不会出现 3a 或 2[4] 这类输入。
• 重复次数位于 [1, 300]，解码结果长度不超过 10^5。

#为什么使用栈

括号具有嵌套结构，最先遇到的 [ 最后闭合，最后遇到的 [ 最先闭合，处理顺序符合后进先出。

例如：

3[a2[c]]

读取内层 2[c] 时，外层的重复次数 3 和已经得到的前缀 "a" 都暂时不能结算。必须先保存它们，等内层得到 "cc" 后，再恢复外层上下文。

这里使用的是“括号上下文栈”，不是单调栈。栈内元素之间没有大小关系。

#状态定义与不变量

扫描过程中维护：

• current：当前括号层已经解码出的内容。
• repeat：最近连续读取、但还没有被 [ 消耗的重复次数。
• stack：从外到内保存所有尚未闭合括号的 [prefix, count]。

处理每个字符前后都保持：

1. current 只属于当前最内层尚未闭合的括号；如果当前没有未闭合括号，它就是最外层结果。
2. 栈中每个 prefix 都是进入对应 [ 前已经完整解码的内容。
3. 栈中每个 count 都是对应括号内容最终需要重复的次数。
4. 栈的深度等于当前尚未匹配的 [ 数量。

#四类字符的处理

#数字

重复次数可能有多位，因此使用：

repeat = repeat × 10 + 当前数字

例如依次读到 "1"、"2" 后，repeat 从 0 变成 1，再变成 12。

#左括号[

[ 表示即将进入一层新的编码内容：

1. 把 [current, repeat] 压栈。
2. 将 current 清空，用来收集新一层内容。
3. 将 repeat 清零，避免影响后续括号。

#字母

字母属于当前层，直接追加到 current。

#右括号]

当前层已经结束，从栈顶取回 [prefix, count]：

current = prefix + current.repeat(count)

因为方括号正确嵌套，所以当前 ] 一定与最近压栈的 [ 配对。

#示例推演

以 s = "3[a2[c]]" 为例：

扫描结束后，栈为空，current 就是完整答案。

#代码实现

思路参考：JoshCrozier/leetcode-javascript。本文重新整理了变量命名、字符判断、状态不变量和复杂度分析；原项目采用 MIT License。

#JavaScript 实现

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function (s) {
    const stack = [];
    let current = '';
    let repeat = 0;

    for (const char of s) {
        if (char >= '0' && char <= '9') {
            repeat = repeat * 10 + Number(char);
        } else if (char === '[') {
            stack.push([current, repeat]);
            current = '';
            repeat = 0;
        } else if (char === ']') {
            const [prefix, count] = stack.pop();
            current = prefix + current.repeat(count);
        } else {
            current += char;
        }
    }

    return current;
};

使用 char >= '0' && char <= '9' 是为了明确只识别 ASCII 数字。原实现的 !isNaN(char) 在本题合法输入下也能运行，但它会把空白字符等可转换为数字的内容误判为数字，不适合作为通用的字符分类方式。

#代码与思路对照

#正确性说明

可以按照扫描字符的四种情况验证不变量：

• 读到数字时，只更新尚未被 [ 使用的 repeat，当前层内容和栈不变。
• 读到 [ 时，将当前层的前缀与重复次数完整保存，再进入空的新层。
• 读到字母时，把它追加到当前层，不影响其他层。
• 读到 ] 时，当前层内容已经完整。由于括号正确嵌套，栈顶恰好是与它配对的外层上下文，合并后得到该外层目前已经解码的完整前缀。

题目保证输入有效。扫描结束时所有括号都已闭合，栈为空；根据不变量，current 正好是整个字符串的解码结果，因此算法正确。

#边界与陷阱

• 多位次数： 12[a] 必须得到 12 个 "a"，数字要逐位累积。
• 嵌套编码： 3[a2[c]] 必须先结算内层 2[c]。
• 相邻编码： 3[a]2[bc] 结算第二段时不能覆盖第一段结果。
• 普通前后缀： abc3[cd]xyz 中括号外的字符也要保留。
• 清空当前层： 读到 [ 后必须令 current = ''，否则内外层内容会混在一起。
• 重置次数： 次数压栈后必须令 repeat = 0。
• 栈中要保存两项： 只保存重复次数会丢失外层前缀，只保存前缀则无法展开。
• 输入有效性： 题目保证格式合法，所以代码没有额外处理孤立括号、缺失次数或空栈弹出。
• 不要使用 shift()： 本题需要后进先出，应使用数组尾部的 push() 和 pop()。

#复杂度分析

设：

• n 为编码字符串长度。
• L 为最终解码结果长度。
• h 为最大括号嵌套深度。

扫描输入和栈操作本身需要 O(n) 时间，但 JavaScript 字符串不可变，repeat() 与字符串拼接会创建新字符串。因此，更精确地说：

• 时间复杂度为 O(n + M)，其中 M 是所有括号结算过程中实际生成、复制的字符串总长度。
• M 通常与输出长度 L 同阶；考虑大量重复次数为 1 的深层嵌套时，同一字符可能在多个层级被复制，保守上界为 O(hL)。
• 所以这份 JavaScript 实现的保守时间上界可以写成 O(n + hL)，而不能只写成 O(n)。
• 空间复杂度为 O(h + L)：栈有至多 h 层，同时保存尚未合并的前缀和正在构造的解码内容。即使不把最终返回值计入额外空间，中间字符串仍可能占用 O(L) 空间。

题目保证 L <= 10^5，否则即使编码字符串很短，解码结果也可能因重复而迅速膨胀。

#替代解法

#递归下降解析

递归函数负责解析当前位置到当前层 ] 之前的内容。遇到普通字母就追加，遇到数字就读取完整次数，再递归解析括号内部。

这种写法与编码文法很接近，但需要正确维护共享下标，且递归栈深度为 O(h)。题目中的输入长度很小，递归深度不会成为实际问题；迭代栈版本则更直接地展示了上下文如何保存和恢复。

#单个字符栈

也可以把字符全部压栈，遇到 ] 后向前弹出到 [，再继续弹出数字并展开。这种方法同样正确，但多位数字需要反向还原，且会频繁操作单个字符，通常不如直接保存 [prefix, count] 清晰。

#面试官递进追问

#1. 栈中的每个元素为什么要同时保存前缀和重复次数？

进入新括号后，当前变量要改为收集内层内容。外层已经解码的前缀和控制当前括号的重复次数都暂时无法结算，必须一起保存，才能在遇到对应 ] 时恢复。

#2. 为什么遇到] 时一定应该弹出栈顶？

方括号正确嵌套，最后打开的括号一定最先关闭。因此当前 ] 对应最近一次遇到的 [，也就是栈顶上下文。

#3. 为什么重复次数要写成repeat * 10 + digit？

这是十进制数字的逐位构造规则。读入新数字相当于把已有数字左移一位十进制位，再加上当前位，因此能正确处理 12、300 等多位次数。

#4. 读到[ 后为什么必须同时清空current 和repeat？

current 已作为外层前缀入栈，新层应从空字符串开始；repeat 已作为该括号的次数入栈，后续数字应重新计数。缺少任意一次重置都会污染内层状态。

#5. 为什么本题不是单调栈？

算法只利用括号嵌套的后进先出关系，栈内元素并不维持递增或递减顺序，也不会根据大小弹栈，因此不属于单调栈问题。

#6. 为什么复杂度不能只看扫描循环写成O(n)？

输入中的 100[a] 很短，输出却有 100 个字符。repeat() 和字符串拼接的成本与产生的字符串长度相关，所以至少要把输出规模和中间字符串复制计入分析。

#7. 如果输入不保证合法，需要增加哪些检查？

需要拒绝孤立的 [ 或 ]、括号前缺少合法次数、数字后没有 [、括号不匹配、非法字符以及可能超过允许上限的展开长度。弹栈前也要检查栈是否为空。

#8. 递归解法与显式栈解法如何取舍？

递归下降更贴近嵌套文法，代码可以很自然；显式栈避免依赖调用栈，并把每层保存的状态展示得更清楚。两者的核心都是保存外层前缀、重复次数和当前解析位置。

#常见错误

• 把每个数字单独当作次数，无法解码 12[a]。
• 遇到 [ 时只保存次数，导致括号前缀丢失。
• 进入内层后没有清空 current，造成内容重复或顺序错误。
• 次数入栈后没有清零，污染下一个编码片段。
• 遇到 ] 时只做 current.repeat(count)，忘记接回 prefix。
• 把本题误认为单调栈，并试图比较栈顶元素大小。
• 复杂度只写 O(n)，忽略输出长度和 JavaScript 字符串复制。

#可迁移总结

• 括号嵌套： 最近进入的上下文最先结束，优先考虑栈或递归。
• 上下文恢复： 入栈的内容应足以让算法在子问题完成后恢复现场。
• 多位数字： 扫描字符串时用 value = value * 10 + digit 累积。
• 一句话记忆： 左括号保存“外层前缀 + 次数”，右括号用“前缀 + 当前层重复结果”完成归并。

#刷题后自测

先只回答第 1 题，再展开后续问题：

1. 在处理 3[a2[c]] 的内层 [ 时，栈顶应该保存什么？

2. 如果读到 [ 后没有把 repeat 清零，哪个输入会最先暴露问题？

3. 为什么 abc3[cd]xyz 可以检验前缀和后缀是否被正确保留？

4. 尝试写出递归下降版本，并指出它的递归终止条件。