1. 题目拆解字符串解码到底在考什么字符串解码LeetCode 394 题是面试里出现频率相当高的一道中等题。我第一次见到它是在一场模拟面试中当时题目摆在面前第一反应是这不就是个括号匹配吗结果上手一写才发现自己把3[a2[c]]这种嵌套结构处理得乱七八糟。后来把这道题吃透之后再看它其实考察的是两件事你能不能把重复次数和字符串内容正确配对以及嵌套结构下你有没有清晰的递归或栈思维。先说清楚题目本身。给定一个经过编码的字符串规则是k[encoded_string]方括号内的字符串会重复 k 次k 保证是正整数。注意输入字符串本身可能包含嵌套的编码块比如3[a2[c]]这种内层套外层的写法也可能包含括号外部的普通字符比如abc3[cd]xyz。输出就是完全解码后的原始字符串。有几个约束值得提前标注k可能不是个位数比如10[abc]100[leetcode]所以解析数字时不能用单个字符去读。嵌套深度没有限制理论上可以写很多层。方括号是成对出现的题目保证输入合法不需要额外做括号校验。从这几个约束能看出这道题想通关至少得解决三个问题多位数的累积解析、嵌套的层级回退、以及普通字符的直接拼接。这三个问题恰好对应了栈解法里三个核心操作也是递归解法里递归入口和出口的设计依据。我见过不少人上来就写正则表达式或者直接调字符串的 replace 方法这种思路在小规模用例上能跑通一旦嵌套层数增加效率和正确性都会出问题。真正的面试考场上面试官期待的往往是手写栈或递归而不是各种语言特性取巧。2. 为什么辅助栈是首选数据结构选型分析解码过程本质上是一个从左到右扫描 遇到 ] 时回退的过程。这种先暂存、后取出的形态天然地指向了栈结构。你可以把它类比成现实中的括号匹配每读到一个[就相当于进入一个新的层级当前上下文需要保存下来每读到一个]就相当于退出当前层级把保存的上下文恢复出来继续往后处理。栈的后进先出特性正好和这种层级的进入退出一一对应。2.1 顺序扫描思路的自然选择从第一个字符开始逐字符扫描不需要回退也不需要两个指针。每个字符只有四种身份数字、左括号、右括号、普通字母。遇到普通字母直接拼到当前字符串尾巴上遇到数字就累积成完整的重复次数遇到[就说明要开辟一个新层把当前已积累的信息压栈保存遇到]就弹出最近的上下文把刚才这一层的字符串重复并拼接回去。这个流程听起来简单但如果你用手写草稿去模拟一遍2[a3[b]]就会发现压栈保存的到底是什么是个容易搞混的点。我见过很多初学者压栈时只压字符串不压数字到]弹出时才发现次数不够用。实际上数字和字符串需要分别用一个栈来维护因为它们的生命周期是不同步的——数字在[之前解析完毕而字符串是在整个[ ... ]内容结束之后才需要被取出来。把这两个栈分开职责边界反而更清晰。2.2 双栈分工数字栈与字符串栈的职责边界我习惯把这两个栈命名为numStack和strStack一个管次数一个管上下文。具体职责如下栈压栈时机弹栈时机保存内容numStack遇到[时遇到]时当前层重复次数strStack遇到[时遇到]时当前层之前的已拼接字符串这里有个非常容易踩的细节strStack压入的不是从开头到现在的所有内容而是进入当前[之前已经拼好的内容。举个例子ab2[c]扫描到2之前cur里已经有ab遇到[时要把ab压栈然后重置cur为空用来累积[ ]内部的c。等遇到]时弹出ab再加上c重复 2 次的结果cc得到abcc。如果你的strStack压入的是整个ab之外还夹带了别的东西拼接顺序就会错乱。这种进入新层前保存现场退出时恢复现场的思路和函数调用时保存栈帧的行为是高度一致的。理解了这一层你会发现递归解法其实是在模拟同一个过程只不过递归用系统栈替我们维护了现场。3. 辅助栈解法完整落地逐字符处理与代码实现这一节直接把代码写出来然后逐段拆解。我用 Java 实现这是面试中最常用的语言之一换到 C 或 Python 思路完全一样只是语法层面的差别。3.1 四类字符的处理规则扫描过程中对每个字符c做分支判断数字字符num num * 10 (c - 0)。这里必须用累积的方式而不是c - 0直接赋值否则12[a]会被误读成先 1 后 2最后变成次数为 2。当初我在100[leetcode]这个测试用例上翻过车就是因为只处理了个位数。左括号[把当前的num压入numStack把当前已拼接的cur.toString()压入strStack然后重置num 0、cur new StringBuilder()。重置这一步极其关键漏掉它内层的内容会和外层残留的字符混在一起。右括号]从numStack弹出重复次数从strStack弹出上一层已拼接字符串把cur的内容重复拼接在弹出字符串后面最后把结果赋值回cur。普通字母直接cur.append(c)包括空格、连字符等非括号非数字字符都走这个分支。这套规则写成代码非常直白但每一个分支的边界条件都值得在注释里标出来。特别是num重置的位置我看到过三种典型错误不在[处重置、不在]之后重置其实不需要、以及重复使用同一个num变量而没有局部保存次数。3.2 完整代码与执行过程追踪class Solution { public String decodeString(String s) { DequeInteger numStack new ArrayDeque(); DequeString strStack new ArrayDeque(); StringBuilder cur new StringBuilder(); int num 0; for (char c : s.toCharArray()) { if (Character.isDigit(c)) { num num * 10 (c - 0); } else if (c [) { numStack.push(num); strStack.push(cur.toString()); num 0; cur new StringBuilder(); } else if (c ]) { int repeatTimes numStack.pop(); StringBuilder prev new StringBuilder(strStack.pop()); for (int i 0; i repeatTimes; i) { prev.append(cur); } cur prev; } else { cur.append(c); } } return cur.toString(); } }我们用3[a2[c]]手动走一遍确认每一步的状态。初始num0cur扫描位置字符numcur当前累积串numStackstrStack033[][]1[0重置[3][]2a0a[3][]322a[3][]4[0重置[3, 2][, a]5c0c[3, 2][, a]6]0acc[3][]7]0accaccacc[][]注意第 6 步弹出numStack得到 2弹出strStack得到a然后把cur里的c重复 2 次拼到a后面得到acc。第 7 步弹出 3 和空字符串把acc重复 3 次得到最终结果accaccacc。这个追踪过程如果你是第一次接触这道题强烈建议在纸上自己画一遍。把每一步的四个状态写出来比你盯着代码看十遍都管用。我面试别人时也经常让候选人走这个例子能完整走对的人基本上代码也不会写错。3.3 复杂度分析与边界用例验证时间复杂度方面扫描是线性的但拼接字符串时prev.append(cur)会涉及字符拷贝。严格来说总操作次数和最终解码后字符串的长度成正比。假设输出长度为 L那么时间复杂度就是 O(L)。如果只看输入字符串长度 n最坏情况下输出可能是指数级增长的比如多层嵌套且每层倍数都很大但在 LeetCode 的测试范围内按输出长度来估复杂度是合理的。空间复杂度为 O(n)主要来自两个栈的存储。numStack保存的层数不会超过输入中[的数量strStack保存的字符串总长度也和输入规模相关。cur本身在拼接过程中会动态膨胀但它最终就是输出的一部分不额外计入辅助空间。边界用例我建议至少覆盖这么几类输入: 3[a]2[bc] 输出: aaabcbc 输入: 3[a2[c]] 输出: accaccacc 输入: 2[abc]3[cd]ef 输出: abcabccdcdcdef 输入: abc3[cd]xyz 输出: abccdcdcxyz 输入: 10[abc] 输出: abcabcabcabcabcabcabcabcabcabc 输入: 输出: 输入: abc 输出: abc最后两个用例容易被忽略。空字符串直接返回空即可没有任何括号时代码会一路走普通字母分支自然拼接出原始字符串。没有括号的输入是最简单的情况但如果你的代码里对numStack或strStack做了不安全的pop()空输入就会抛异常。我在实现时习惯一开始就加一个判空逻辑虽然题目不一定会给空串但防御性编程总没有坏处。4. 递归下降解法用子问题消解嵌套括号栈解法能解决绝大多数场景但有些人会更喜欢递归写法。原因也很简单嵌套结构天然适合用递归的子问题来描述遇到[就递归处理内部处理完返回再把结果重复拼接。这样代码读起来更贴近问题的数学定义不需要手动管理两个栈。4.1 递归的核心设计全局指针与返回值递归解法里有一个非常关键的设计决策要不要用全局指针。因为递归函数需要知道当前扫描到输入字符串的哪个位置如果每次递归都把剩余子串传进去会产生大量字符串切割空间和时间都不划算。我建议用一个类级别的成员变量index来记录当前位置所有递归调用共享它。实现如下class Solution { private int index 0; public String decodeString(String s) { return dfs(s); } private String dfs(String s) { StringBuilder sb new StringBuilder(); int num 0; while (index s.length()) { char c s.charAt(index); if (Character.isDigit(c)) { num num * 10 (c - 0); index; } else if (c [) { int repeat num; num 0; index; String inner dfs(s); while (repeat 0) { sb.append(inner); repeat--; } } else if (c ]) { index; return sb.toString(); } else { sb.append(c); index; } } return sb.toString(); } }这里最值得注意的地方是int repeat num; num 0;这行。我最初写的时候在[之前忘了把num保存下来结果递归返回后num已经被内层调用修改了外层重复次数变成了内层的数字测试3[a2[c]]时输出了accacc而不是accaccacc。在递归写法里num是共享变量内层递归会改它所以必须在进入递归前先保存副本。另一个容易出错的地方是]分支的处理。递归函数返回的时机有三个遇到]、扫描到字符串末尾、或者内部不再有可处理字符。当遇到]时需要先把index后移一位跳过这个括号再返回结果。如果忘记移动index外层递归会反复读取同一个]造成死循环。4.2 两种解法对比与适用场景从面试官的角度看栈解法和递归解法都能通过但有细微的偏好差异。栈解法更符合显式控制状态的工程思维适合描述为扫描每个字符遇到右括号就回退合并递归解法更符合分治的算法思维适合描述为遇到左括号就递归求解子问题。两者在时间复杂度上没有本质差别但递归对系统栈的消耗更大如果嵌套层数极深可能出现栈溢出不过 LeetCode 的测试用例不会极端到那种程度面试中不用担心。我个人在面试中的建议是先讲栈解法把双栈的分工说清楚然后主动提一句其实也可以递归遇到[时递归处理内部子串这样能展示你思维的多元性。不要两种都写时间不够而且容易写着写着搞混。如果面试官追问哪种更好就用工程实现上栈更稳递归在代码表达上更贴近问题定义这个话术回答。还有一个细节递归解法的代码对空输入天然友好while (index s.length())直接跳过返回空字符串不需要额外特判。这也是它代码更简短的一个原因。5. 面试中的高频追问与进阶变体这道题做完只是第一步。面试官通常不会只满足于你 AC 了而是会抛出追问来测试你的理解深度。下面这几个问题是我在实际面试中遇到过的或者从其他候选人那里听来的整理出来供大家参考。5.1 最容易翻车的三个细节第一多位数解析。这是最常见的低级错误。12[a]里的12必须被解析成十二而不是一和二。正确做法是num num * 10 (c - 0)并且每次遇到[后清零。有些人会在]之后忘记清零导致下一次解析时数字翻倍这种 bug 推荐用10[a]这种多位数用例来测。第二拼接顺序。]弹出后的拼接顺序是prev cur 重复 repeatTimes 次而不是cur 重复 prev。这个顺序一旦颠倒输出就是反的。我曾经在2[abc]3[cd]ef上测试时因为拼接顺序写反得到了abcabccdcdcdef的正确结果但完全不知道是碰巧对了还是逻辑对了后来换了ab2[c]这种不对称用例才暴露问题。所以测试用例一定要选拼接前后不对称的。第三栈为空时的 pop。题目保证输入合法所以理论上不会出现空栈 pop。但如果你用Stack类的pop()方法而测试用例包含格式错误的输入虽然 LeetCode 不会给就会抛异常。在工程写码习惯上至少要知道 Deque 的poll()和pop()在空栈时的行为差异前者返回 null后者抛异常。5.2 变体题目与扩展思路这道题的变体在面试中出现率很高最常见的几个方向逆序解码编码串可能是从右往左生成的比如a2[c]会在原题中变成2[c]a吗不会但变体中可能出现2[c]a这种后缀式编码这时候从右往左扫描遇到[时做合并思路是对称的。多层嵌套加多位数混合比如3[a]2[bc]是基本款3[a2[bc]d]是中档款2[3[a]4[b]]是难度稍高的嵌套加并列款。建议把这几个用例都测一遍。解码后的长度计算不要求输出完整字符串只要求输出解码后的长度这可以用动态规划或者栈来避免真正拼接字符串适合考察候选人的空间优化意识。我自己的经验是把题做对不难难的是把题讲清楚。面试时你如果能主动画出那道3[a2[c]]的状态变化表把numStack和strStack每一步的内容说出来面试官对你的印象会明显好于只说我用栈做的。这就是为什么我在文章里花了那么大篇幅做状态追踪——这既是检验自己思路的手段也是面试中展示思维过程的好方式。最后分享一个我自己的做题习惯拿到这类字符串解析题先不急着写代码而是把输入字符串写在纸上用一个很长的嵌套用例比如2[3[a]4[b]5[c]]手动走一遍流程标出每一层进入和退出时的状态。这一步做顺了后面的代码基本是一气呵成的。栈和递归两种解法我都写过不下五遍现在再看到字符串解码脑子里浮现的已经不是代码而是那张状态变化表。掌握到这种程度这道题才算真正过关。