力扣hot100榜单里的第394题“字符串解码”是我见过把“栈”这个数据结构讲得最透彻的一道题。题面看起来吓人给你一串带数字和方括号的字符串比如3[a2[c]]让你按照规则展开成accaccacc。很多人第一次做的时候会被嵌套括号绕晕要么在纸上模拟半天要么一上来就想用复杂的递归处理结果把自己绕进去。实际上它的核心思想非常朴素一个栈装数字一个栈装字符串遇到[就保存现场遇到]就恢复现场并翻倍拼接。这篇文章我会把这道题从原理到实现完整拆开包括栈解法和递归解法两种思路再加上我实际刷题过程中踩过的坑、Debug实录以及一些常规题解里不会写的细节。不管是第一次刷hot100的新手还是想系统整理“括号匹配/嵌套解析”类题目的朋友都能从里面拿到直接能用的东西。1. 题目理解与核心难点1.1 这道题到底在考什么先看一眼规则。编码格式是k[encoded_string]其中k是正整数表示方括号内的字符串重复k次。注意方括号是可以嵌套的比如3[a2[c]]意思是先算内层2[c]得到cc再算外层3[acc]得到accaccacc。再看两个官方样例2[abc]3[cd]ef输出abcabccdcdcdef。这里2[abc]是abcabc3[cd]是cdcdcd最后再接一个普通字符ef。3[a]2[bc]输出aaabcbc。输入只包含小写字母、数字和方括号并且保证括号成对出现、数字一定是正整数。这意味着我们不用做合法性校验可以专心处理解码逻辑。这道题表面上叫“字符串解码”本质上考的是“嵌套结构的解析”。和它同类的题目包括20. 有效的括号、71. 简化路径、227. 基本计算器这些题的核心都是同一个点当表达式结构出现嵌套时如何用栈来保存和恢复上下文。你如果把这一题的栈思路吃透其他嵌套类题目基本就是换一层皮。1.2 为什么不能凭感觉硬解很多人拿到这题的第一反应是从左往右扫描看到3[a]就直接把a重复三次拼进去。这个思路在无嵌套情况下是对的但一遇到3[a2[c]]这种嵌套就崩了当你扫描到内层2[c]时你还得记得外层有个3[等着把整个结果再重复三遍。这种“先记住外层状态处理完内层后再回来继续”的需求天然就是后进先出的结构所以栈几乎是唯一自然的解法。另外有两个容易忽略的细节。第一数字可能是多位的比如12[ab]你不能只解析一个字符。第二数字和括号之间可能夹杂普通字符比如2[abc]3[cd]ef末尾的ef不属于任何括号它得被原样拼接在最终结果里。还有个很有意思的现象很多刷题网站上会把这道题和“动态规划”热词关联到一起甚至有人误以为它是一道DP题。这其实是个误会。动态规划要求子问题重叠、需要做状态转移和选择而字符串解码的每一步都是确定性的括号结构天然形成一棵树每个子树只出现一次没有重叠计算也不需要“取最优”。它真正的身份是“栈”题或者说是“递归/DFS”题。搞清楚这一点很重要否则你会带着错误的算法思路去硬套状态转移方程越套越乱。2. 栈解法一次遍历拆掉所有嵌套2.1 栈里到底存什么栈解法需要两个栈一个存数字一个存字符串。为什么是两个而不是一个因为遇到嵌套时我们需要同时保存两层信息外层已经拼好的字符串以及外层括号的重复次数。用一个栈存数字另一个栈存字符串这样在弹出]的时候一次就能把这两个信息都拿到。除了两个栈还要维护两个临时变量curNum当前正在解析的数字。遇到[时这个数字就确定了应该压入数字栈并清零。curStr当前层已经累积的字符串。遇到字母时追加遇到[时压入字符串栈并重置为空。这里可以类比一个场景你在写文章时写到了一个引用块引用块里又套了一层引用块你会先把当前段落的内容夹在书签里然后专心写引用块里的内容写完后再把书签取出来把两部分拼在一起。栈就是那叠书签每一次[就是往书签堆里压一层现场。2.2 手把手模拟2[3[a]b]为了把流程彻底讲清楚我用一个稍微复杂一点的例子2[3[a]b]来逐步模拟。这个串的意思是内层3[a]生成aaa然后当前层变成aaab最后外层重复两次得到aaabaaab。下面这张表是每一步执行完后的状态步骤读入字符操作说明curNumcurStr数字栈字符串栈12读取数字2[][]2[保存当前层级状态0[2][]33读取数字3[2][]4[保存当前层级状态0[2, 3][, ]5a往当前层字符串追加0a[2, 3][, ]6]弹出3和拼接0aaa[2][]7b往当前层字符串追加0aaab[2][]8]弹出2和拼接0aaabaaab[][]第6步是理解重点遇到]时先弹出数字栈顶的3再弹出字符串栈顶的把当前curStr重复3次后拼接到弹出的字符串后面。这个拼接顺序是已弹出的外层字符串 当前串重复次数不能反过来。第8步同理弹出数字栈的2和字符串栈的把curStr也就是aaab重复两次得到最终结果aaabaaab。2.3 多位数解析与代码实现有了上面的流程代码其实非常短。用Python写是这样def decodeString(s: str) - str: num_stack [] str_stack [] cur_num 0 cur_str for ch in s: if ch.isdigit(): cur_num cur_num * 10 int(ch) elif ch [: num_stack.append(cur_num) str_stack.append(cur_str) cur_num 0 cur_str elif ch ]: repeat_times num_stack.pop() prev_str str_stack.pop() cur_str prev_str cur_str * repeat_times else: cur_str ch return cur_str注意isdigit()分支里的写法cur_num cur_num * 10 int(ch)。这一步专门用来处理多位数。比如遇到12[ab]先是1和2依次进来curNum先变1再变12直到遇到[才压栈。如果你写成cur_num int(ch)那12[ab]就会变成先重复一次再重复两次完全错乱。遇到[时为什么必须把curStr也压栈并重置因为新的一层开始后当前curStr属于外层如果不保存下来等内层处理完就丢了。遇到]时的prev_str cur_str * repeat_times则是整个算法的核心它同时完成了两层级别的拼接把结果重新交还给外层。这一段代码的正确性可以这样验证输入3[a2[c]]最后返回accaccacc。你可以在纸上按表格方式手动跑一遍确认每个状态都吻合。时间复杂度上解码后的字符串长度为S所有字符最终都会被拼接进结果因此是O(S)。空间上两个栈的最大深度等于嵌套层数也是O(S)。3. 递归解法用DFS思维看嵌套结构3.1 为什么递归也天然成立栈解法是从“状态保存与恢复”的角度解题但嵌套结构本身还有另一种完全对偶的视角递归。你可以把k[...]看作一个子问题[...]里面的内容就是一个新的、规模更小的解码字符串。处理完内层后把结果重复k次返回给上层。这本质上就是对一棵“括号树”做DFS遍历。递归写法最适合那些“括号嵌套很直观”的题目尤其是你脑子里已经把输入字符串画成了一棵树根节点是整串遇到[就往下走一层遇到]就回到上一层。3.2 递归实现的关键细节递归比栈写法更短但它有一个大坑索引如何推进。如果你在递归函数里用局部变量i来遍历字符串你会发现递归返回后外层不知道内层处理到哪里了。解决办法是把索引提升为成员变量或者通过返回值把新索引带上来。这里我给出一个用成员变量的Python实现class Solution: def decodeString(self, s: str) - str: self.index 0 def dfs(): res while self.index len(s): ch s[self.index] if ch.isdigit(): k 0 while self.index len(s) and s[self.index].isdigit(): k k * 10 int(s[self.index]) self.index 1 self.index 1 # 跳过 [ inner dfs() self.index 1 # 跳过 ] res inner * k elif ch.isalpha(): res ch self.index 1 elif ch ]: break return res return dfs()有几个细节必须说清楚。第一数字解析循环结束后self.index一定指向[所以需要self.index 1跳过左括号再进入递归。第二递归返回时self.index刚好停留在]上此时需要再self.index 1跳过右括号。第三elif ch ]分支里不能self.index 1因为右括号的跳过由上一层负责否则外层递归就不知道内层结束的位置了。这些逻辑环环相扣错一个就会死循环或者越界。第四res inner * k这行是在当前层累积结果。注意它和栈解法的prev_str cur_str * repeat_times在本质上是同一个操作只是递归把“保存外层现场”这件事交给了函数调用栈来做不需要自己维护状态。3.3 两种方案如何取舍对比维度栈解法递归解法核心思路显式栈保存上下文迭代处理函数调用栈保存上下文DFS处理代码长度稍微长一点但逻辑直白更短但对索引推进要求高出错概率容易错在拼接顺序容易错在索引和括号跳过面试展示推荐优先讲好沟通作为进阶优化展示代码能力调试难度状态可以用表格记录好查递归深度一大精神状态容易受考验我个人建议面试时先说栈解法因为它最贴近“处理嵌套结构”的直觉代码也容易现场写对。如果面试官追问有没有其他思路再补充递归版本顺便解释两种方案的空间本质都是栈只是一个显式一个隐式。4. 常见误区与Debug实录4.1 数字只取一位的惨痛教训我第一次写这题时天真地认为数字都是一位数结果遇到12[a]就变成了1[a]和普通字符2的拼接输出完全不可理喻。这个问题在刷题时实在太常见了尤其是见过很多题目的输入范围都比较温和之后很容易放松警惕。解决办法只有一个在isdigit()分支里用循环累乘的方式解析完整数字不要看到一位数就想当然。4.2 拼接顺序写反的后果栈解法里最核心的一句话是cur_str prev_str cur_str * repeat_times。如果把顺序写成cur_str * repeat_times prev_str在简单场景下可能碰巧对但在嵌套场景下必错。我举一个具体例子输入3[a2[b]]。正确流程内层2[b]得到bb外层把abb重复3次结果是abbabbabb。如果顺序写反内层得到bb后拼成bb加外层前缀的空串看起来还没问题但再往上一层就会把外层已经累积的内容放在重复结果的后面最终字符串的内容顺序就会颠倒。这类错在单层测试用例下很难发现所以我后来总结了一个经验设计测试用例时一定要包含“外层有前缀”的场景比如2[ab3[c]]这样才能暴露拼接顺序问题。4.3 递归解法中索引不推进递归写法里最常见的Bug就是忘了self.index 1或者在错误的位置推进索引。这个问题比栈解法隐蔽得多因为它不一定报错很多时候表现为死循环或者漏掉字符。我调试时常用的一个办法是在递归函数开头加一句打印print(findex{self.index}, char{ch}, res{res})然后把3[a2[c]]作为输入跑一遍逐行观察index是否按预期越过括号。只要看到某一行index没有变化基本就能定位到是哪一步漏了推进。4.4 对特殊输入考虑不足题目保证了输入合法但不代表你可以不考虑健壮性。我刷题时会额外测这些边界用例10[a]验证多位数解析。3[a]2[b]验证多个顶层重复块拼接。abc3[de]验证括号外普通字符与括号区块相邻。2[ab3[c]]验证嵌套且外层有前缀。3[a2[c]]验证深层嵌套。把这些用例都跑通基本可以放心提交了。4.5 一份真实的Debug记录拿3[a2[c]]举例栈解法调试时可以把每次遇到]后的curStr打印出来你会看到这样的输出第一次遇到]时弹出数字2和字符串curStr从c变成cc。第二次遇到]时弹出数字3和字符串curStr从acc变成accaccacc。如果你发现第二次拼接结果不对就检查prev_str是否还是。这个prev_str应该是遇到3[a时压栈的那个空串。如果它变成了其他内容说明你压栈的时机不对——大概率是压栈前没有把curStr重置为空。5. 从hot100看这道题的价值与刷题策略5.1 这道题在hot100里的定位hot100榜单里其实很少直接考察“动态规划”这种大而全的知识点更多是混合题型。网络上经常能看到“hot100动态规划”这样的合集标签那只是把动态规划题目单独整理出来的刷题清单不代表每道题都是DP。394这个题就是一个典型它被归入栈/递归专题和动态规划没有关系。区分题型有一个简单标准如果题目需要你在多个选择中“取最优”比如最大、最小、最长那大概率是动态规划如果题目只是要求按照某种规则“展开”“模拟”一个确定性结构那大概率是栈、递归或模拟。字符串解码的每一步结果都是唯一确定的没有任何“选哪条路更好”的余地所以它是栈题不是DP题。很多人被热词误导以为要写dp[i]来表示前i个字符串的解码结果结果发现根本没有状态转移方程可写白白浪费时间。这个教训值得记下来。5.2 从这一题延伸出去的同类问题字符串解码练熟后可以顺势把这几道题一起刷了20. 有效的括号最基础的括号匹配理解栈的入栈出栈时机。71. 简化路径用栈处理路径中的..和.体会栈在规范文本中的作用。856. 括号的分数嵌套结构的计分考查如何维护层级信息。227. 基本计算器 II用栈处理算术表达式的优先级思路有共通之处。32. 最长有效括号这道题才真正涉及动态规划与栈的结合可以用来对比和394的区别。这几道题都围绕一个主题看到嵌套和配对第一反应就是栈。练完它们你对这类题型的敏感度会上一个台阶。5.3 刷题建议与测试方法我的建议是遇到这类题不要一上来就写代码。先在纸上把字符串里的括号配对画出来比如3[a2[c]]连一下左右括号你会看到它天然是一棵两层树。然后在这棵树上决定用栈还是递归最后再落实到代码。测试用例的设计也很重要。我一般固定准备五个用例无嵌套、嵌套一次、多位数、连续重复块、括号外字符混排。每个用例跑通后再提交避免因为样例太少而漏掉边界问题。如果本地调试条件和线上环境一致我还会写一个暴力展开对照组来验证随机用例的结果。另外如果用的是Java或C要注意字符串拼接性能。Java里建议在最后返回时用StringBuilder或直接拼接因为String是不可变对象循环内频繁会产生大量中间对象。Python的字符串虽然也是不可变的但题目规模通常不大直接用乘法拼接问题不大。C则要注意std::string的和substr操作的开销。这些小细节看着不起眼在面试手写代码时却可能被追问。我个人做这类题最大的体会是嵌套结构题的错误往往不是“不会写”而是“状态乱了”。只要把每一步涉及的curNum、curStr和两个栈的状态列清楚代码跟着状态走基本一遍就能写对。最后再分享一个实用小技巧如果你调试栈解法时实在找不到问题把每一步执行后的四个状态打出来和手算的表格逐列对比差异出现的那一行就是Bug所在。这个方法帮我节省过无数时间强烈建议你也试试。