字符串解码
Decode String
解码形如 k[encoded] 的字符串，支持嵌套和多位数字。
在力扣中练习题目描述
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
测试用例保证输出的长度不会超过 105。
示例 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 <= 30s由小写英文字母、数字和方括号'[]'组成s保证是一个 有效 的输入。s中所有整数的取值范围为[1, 300]
解题思路
双栈 · 迭代
数字栈存重复次数，字符串栈存外层已解出的内容
括号可能嵌套，所以需要记住“进入这一层之前”的状态。用两个栈：
counts存每层的重复次数；strs存每层外面的字符串。
读到数字就累积 num；读到 [ 就把 num 和当前 cur 压栈，然后清零；读到字母就追加到 cur；读到 ] 就弹出 k 和外层字符串，把 cur 重复 k 次接回去。
遇到数字先累积；遇到 [ 把 num 和外层 cur 压栈；遇到 ] 弹出并重复拼接。
自拟串 "3[a2[c]]4[b]" 有两层嵌套：内层 2[c] 先展开成 cc，外层再把 a+cc 重复三次；最后的 4[b] 与外层互不影响。
进入新一层：把重复次数和外层字符串压栈，num、cur 清零。
- depth
- 2
每个字符只处理一次，重复拼接的总量等于输出长度，时间与输出规模同阶；空间 O(嵌套深度 + 输出)。
易错点
- 数字只取一位：遇到 12[ab] 会解码错。
- [ 时忘记保存外层字符串：嵌套结束后接不回去。
- ] 时先拼再弹栈：顺序反了会用错外层。
- 用递归但忘记跳过 ]：会在右括号处死循环。
递归 · 解析每一层
遇到 [ 就递归解析内层，返回后重复拼接
代码更短，但递归深度等于嵌套层数，极深输入可能栈溢出；双栈版把调用栈显式化。
把每一对括号看成一次递归：遇到 [ 就进入下一层，解析到匹配的 ] 返回内层字符串，再按前面的数字重复。
递归函数的循环在遇到 ] 或字符串结束时退出，正好把当前层的内容交回给调用者。数字在每层各自累积，不会互相干扰。
它和双栈版状态一一对应，只是把“保存外层字符串”交给调用栈。
- 1逐字符解析当前层。
- 2遇到 [ 递归解析内层。
- 3返回后按 num 重复并接到当前结果。
- 4遇到 ] 或末尾返回当前层字符串。
易错点
- 递归返回后忘记跳过 ]：外层会把右括号当普通字符。
- num 没有在每层清零：内层数字污染外层。
- 重复次数很大时直接递归拼接：输出规模本身无法避免。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
s = "3[a2[c]]4[b]"遇到数字先累积；遇到 [ 把 num 和外层 cur 压栈；遇到 ] 弹出并重复拼接。
查看 C++ 代码
延伸阅读
- 括号嵌套题通常需要两个栈：一个存数值，一个存“进入括号前”的上下文。
- 如果只需要求解码后的第 k 个字符，可以边解析边计数，避免构造完整字符串。