字符串解码是算法题里一道经久不衰的经典题目常年出现在各类面试题库的“栈与递归”分类下。它的输入长这样3[a2[c]]要求按照规则输出accaccacc。规则本身一句话就能说清k[encoded_string]表示把方括号内的字符串完整重复 k 次方括号可以嵌套数字只会作用在它正后方的那一个括号块上。很多第一次看到这道题的人都会觉得“这有什么难的写个循环展开不就行了”。但真到了手写环节尤其是面对2[a3[b]]这种多层嵌套、100[leetcode]这种大数字、还有字符串前后夹杂普通字母等场景时不少人会在几分钟之内连续翻车。原因在于题目表面上考的是“字符串展开”实际考的是“遇到嵌套结构时你怎么管理已经读到的状态”。而这个管理方式恰好是栈这种数据结构最擅长的事。这篇文章不打算只贴一个标准答案完事。我会从问题本质拆起把栈的思路拆成状态转移、单栈双栈写法、递归实现、测试用例矩阵、复杂度和调试技巧全部讲透最后聊聊它和模板引擎、压缩还原之间的真实联系。无论你是准备面试的学生还是日常需要写配置模板解析的工程师这篇内容都值得花二十分钟慢慢看。1. 问题本质与整体设计思路1.1 题目的真实考点嵌套状态的管理字符串解码从表面看是一道“模拟题”按规则把字符串展开就行。但如果你真的试着用最朴素的方式去做比如从头到尾读字符、遇到数字就记下来、遇到[就开始累积、遇到]就重复拼接很快会遇到一个尴尬的问题内层括号展开的时候外层已经读到的字符串放在哪里以2[a3[b]]为例。读入2[的时候你知道外层需要重复两次但还不知道括号里会装什么。继续读到a当前字符串变成了a。接着读到3[b]问题来了内层3[b]展开结果是bbb它必须和外层的a拼成abbb然后再整体重复两次才是最终答案。可是在读内层的时候a还没有被重复它不能被直接追加到结果里只能暂时存在某个地方等内层算完再取出来拼上。这个“先存起来、等内层算完再取出来”的过程正好符合栈的后进先出特性。你可以把它想象成一层叠一层的盘子最先放进栈底的最外层状态要等所有内层状态都处理完才能拿出来而最后放进去的内层状态反而最先被取出和处理。所以这道题真正在考的东西可以拆成四点对嵌套结构的敏感度。遇到[意味着进入更深一层遇到]意味着回到上一层每一层之间的状态必须隔离。状态保存与恢复。进入内层之前的重复次数、外层已拼好的字符串必须被完整保留内层结束后要无缝恢复。数字解析的完整性。重复次数可能是一位数也可能是两位数、三位数不能只读一个字符就完事。字符串拼接的顺序。展开3[ab]时是ababab拼到外层前缀时方向不能反。这四点综合起来其实更像是在考察“把一段带嵌套规则的结构化文本正确解析为普通文本”的能力。这种能力在各类文本解析器、模板引擎、配置读取工具中都会用到。也正因为如此它比单纯背几种排序算法要更有训练价值。1.2 状态转移视角把读字符抽象成四个动作我个人在写解析类代码时有个习惯先不急着敲键盘而是把“读到什么字符该做什么事”列成一张状态表。字符串解码的状态表非常清晰一共就四类情况读到的字符当前动作效果普通字母追加到当前字符串cur累积当前层的文本数字按位累加进num解析完整的重复次数[把(num, cur)压栈清空cur和num进入内层外层状态进栈保护]弹出最近的(num, prev)把cur重复 num 次再拼到prev后面内层结算完毕恢复外层状态一旦把输入映射成这四个动作写代码就变成了“照着表翻译”。你会发现这道题并不需要复杂的语法分析也不需要预处理只需要一个循环遍历字符串按字符类型走不同的分支。这里有一个容易被忽略的关键点数字和[是一对组合。题目保证数字后面一定跟着[这意味着读到数字时其实是在向自己发出一个信号——“接下来会有一个嵌套块要进入”。数字和[之间的状态变化是有强关联的数字负责记录“这个块要重复几次”[负责触发“外层状态入栈当前层开始解析”。把这两个动作合起来理解代码就不容易写散。用状态表的视角去看很多新手犯的错误就很容易解释了。比如忘记在[时清空cur本质上是在“进入内层”这个动作里漏掉了“重置当前层状态”的一步。再比如]拼接顺序反了本质上是“外层前缀 内层重复结果”的顺序写反了。状态表会逼你把这四步的因果关系想清楚。1.3 为什么栈能和嵌套结构完美对应嵌套结构的解析天然是“内层先结算外层后结算”而栈的后进先出特性恰好就是这种顺序的抽象。你也可以不用栈用递归因为函数递归本质上是借用了系统调用栈进入内层递归时外层的局部变量自动压在调用栈里内层返回时自动弹出。但为什么大多数标准答案更推荐显式使用栈因为递归的方案虽然直观却有一个隐藏的负担每次递归调用都要付出函数调用的开销而且在某些语言里递归深度过大还可能带来调用栈溢出的风险。字符串解码的嵌套深度虽然通常不会特别深但作为一名严谨的开发者显式栈方案在可控性和可解释性上确实更胜一筹。从另一个角度讲栈方案也更好调试。你可以在任意时刻把栈里的内容打印出来直接看到“已经保存了几个外层状态”“每个外层状态的重复次数和前缀是什么”。这种透明性是递归方案很难提供的。理解了“栈 嵌套状态的存储体”这一点后面所有代码版本——无论单栈、双栈本质上都是在这个大框架下的变量。2. 核心实现方案拆解2.1 单栈写法关键在于入栈出栈的时机单栈写法是最经典的实现。栈里的每个元素保存两个信息进入这层之前的重复次数以及进入这层之前已经拼好的字符串。用pairint, string或者一个小的结构体来存都可以。我用 C 写一个标准版本string decodeString(string s) { stackpairint, string st; string cur ; int num 0; for (char c : s) { if (isdigit(c)) { num num * 10 (c - 0); } else if (c [) { st.push({num, cur}); num 0; cur ; } else if (c ]) { auto [prevNum, prevStr] st.top(); st.pop(); string tmp cur; for (int i 1; i prevNum; i) { tmp cur; } cur prevStr tmp; } else { cur c; } } return cur; }写这个版本时有三个细节要特别注意。第一数字累加。num num * 10 (c - 0)保证了12[a]正确解析为重复 12 次而不是先读 1 再读 2 变成两次不同的重复。这个写法在遇到多位数字时是唯一的正确写法。第二[压栈后立刻清空cur和num。这是整个算法里最容易被忽略的一步。cur不清空内层字符就会错误地拼在外层字符串后面num不清空下一个数字块就会带上旧值。第三]拼接时先重复当前字符串再拼到外层前缀后面。cur本身就是当前层已经解析好的完整字符串对它重复prevNum次得到tmp然后把tmp追加到prevStr后面最后回填给cur。这个顺序如果反了嵌套案例会立刻出错。单栈版本的优点是代码短、逻辑集中一行分支对应一个字符类型很容易读。缺点是栈元素里携带了字符串遇到特别长的嵌套时会有一定拷贝开销。这个开销在普通面试环境下可以忽略但如果输入规模很大可以考虑后面的双栈优化或者移动语义优化。2.2 双栈写法数字栈与字符串栈的分工双栈版本在工程思路上更清晰一个栈专门存数字一个栈专门存字符串。它的理念是把“重复次数”和“前缀字符串”这两种不同类型的状态分开管理互不干扰。string decodeString(string s) { stackint numSt; stackstring strSt; string cur ; int num 0; for (char c : s) { if (isdigit(c)) { num num * 10 (c - 0); } else if (c [) { numSt.push(num); strSt.push(cur); num 0; cur ; } else if (c ]) { int k numSt.top(); numSt.pop(); string prev strSt.top(); strSt.pop(); for (int i 0; i k; i) { prev cur; } cur prev; } else { cur c; } } return cur; }双栈版本和单栈版本在逻辑上完全等价但可读性更强。遇到]时你从数字栈拿出来的东西明明白白是一个整数从字符串栈拿出来的是一个前缀两者的语义不会混淆。在工程实践中这种“一类状态一个栈”的写法也更符合单一职责原则方便后续扩展。比如将来要支持k{xxx}花括号只需要在分支里增加一种括号判断不用改动栈元素的结构。不过双栈版本也有一个轻微冗余两个栈分别存储数字和字符串如果每个[都会成对产生压力和弹出那么两个栈的长度始终相等它们在逻辑上其实可以合并成单栈里的一个pair。两种写法各有优势我建议面试时都可以提一嘴单栈紧凑双栈清晰本质一样。2.3 递归写法全局指针的精髓递归解法是另一条重要路线。它不需要显式声明栈而是利用系统调用栈自动保存外层状态。核心设计有两个一个全局下标指针记录读取进度一个递归函数负责解析“从当前位置开始直到某个]结束”的完整块。用 Python 写一个递归版本class Solution: def decodeString(self, s: str) - str: def dfs(): res [] k 0 while self.i len(s): ch s[self.i] if ch.isdigit(): k k * 10 int(ch) self.i 1 elif ch [: self.i 1 inner dfs() res.append(inner * k) k 0 elif ch ]: self.i 1 return .join(res) else: res.append(ch) self.i 1 return .join(res) self.i 0 return dfs()这个版本的巧妙之处在于递归函数的返回值就是“当前括号块完整解析后的字符串”。当它遇到[时递归调用自己内层的返回结果就是整个内层块的展开值当它遇到]时直接返回当前累积结果。内层返回后外层立刻拿 inner 去乘上已经记录的 k 值。我在模拟面试中见过不少人在递归写法上踩同一个坑试图把i作为局部变量传入递归函数然后在递归内部修改它。这样做不是不行但你很快会发现自己需要处理“内层递归把 i 改了之后外层如何拿到更新后的 i”的问题。最省心的做法就是把它做成成员变量或者用长度为 1 的列表[i]作为包装让所有递归层级共享同一个可变的读取位置。递归版本的另一个优势是逻辑跟人类思考方式高度一致。人看到3[a2[c]]时的自然想法就是外层重复三次里面是一个a2[c]而a2[c]又需要先算2[c]。这种“遇到问题就将其拆成子问题”的思路正是递归的思维模式。所以很多面试者在第一直觉里会选择递归这完全合理。两种方案都掌握才能在面试时游刃有余地切换思路。3. 实操过程手写代码与测试3.1 用3[a2[c]]完整走一遍执行流程理论说再多不如亲手把执行流程走一遍。我强烈建议你用一张纸照着下面的表格手动模拟单栈版本的每一步。这个动作看似笨拙却是把入栈出栈时机彻底刻进脑子里最有效的方式。以3[a2[c]]为例初始状态cur num 0栈为空。步骤读到的字符执行动作cur 变化栈的状态13num 3空2[压入 (3, )cur 清空[(3, )]3acur 追加 aa[(3, )]42num 2a[(3, )]5[压入 (2, a)cur 清空[(3, ), (2, a)]6ccur 追加 cc[(3, ), (2, a)]7]弹出 (2, a)cur 重复 2 次得到 cc拼到 a 后面acc[(3, )]8]弹出 (3, )cur 重复 3 次得到 accaccacc拼到 后面accaccacc空第 5 步是整个过程的转折点。读到内层[时当前cur是a它必须被压入栈中保存同时cur被清空。如果这里不清空cur第 6 步的c就会追加到a后面变成ac第 7 步重复 2 次后得到acac整个结果立刻错误。我建议你再自己手动走一遍2[a3[b]]重点感受出栈时prevStr和cur的拼接顺序。当你在纸上画过两三个用例之后遇到这类题目基本不会再被“什么时候清空”“什么时候拼接”这类问题绊住。3.2 测试用例矩阵边界条件全覆盖写完代码只是第一步真正的考验在于能不能写出覆盖各种边界的测试用例。我在自测时通常会准备这样一张矩阵输入期望输出考察点3[a]2[bc]aaabcbc多个独立块顺序连接3[a2[c]]accaccacc一层嵌套2[abc]3[cd]efabcabccdcdcdef块与普通字符混排100[leetcode]leetcode 连续 100 次大数字、单块展开3[z]2[2[y]pq4[2[jk]e1[f]]]zzzyypqjkjkefjkjkefjkjkefjkjkefyypqjkjkefjkjkefjkjkefjkjkef多层嵌套加混合字符3[]空括号块[]极简空块aa无数字无括号普通纯字符串这里有一个边界要特别说明3[]这一类用例部分版本允许空括号块结果为空字符串也有版本规定数字后一定不是空块。不管哪一种代码都应该优雅处理遇到[照常压栈遇到]时 cur 为空重复 k 次结果也是空整体不会报错。我在面试时通常主动提一句“我会兼容空块同时跟面试官确认这算合法输入吗”这是一个很好的沟通信号说明你考虑周全。还有一个值得注意的测试点输入中数字极大比如100000[abc]。虽然输出会长到无法实际验证但算法本身不会死循环只是拼接次数变多。这类测试主要用来确认代码没有性能陷阱以及没有因为数字位数造成整数溢出——如果题目环境是 32 位整数超大数字理论上要谨慎处理不过常规题目中重复次数不会超过 int 范围。3.3 多语言实现差异与性能取舍同一类逻辑在不同语言里会有不同的实现重心。我把它们放在一起对比方便你结合自己的主力语言选择最优写法语言核心注意点推荐做法Python字符串不可变多次会创建大量中间对象用列表收集片段最后.join(list)Cstd::string支持追加压栈时会拷贝字符串数据量大时可用移动语义或者用std::vector模拟栈JavaString不可变Stack类自带同步锁使用StringBuilder和ArrayDeque以 Python 为例我在快速原型阶段经常用列表暂存字符cur_chars [] # 遇到普通字符 cur_chars.append(ch) # 遇到 ] cur .join(cur_chars) # 之后进行重复拼接如果全程用cur ch也不是不能跑但对超长输出用例来说性能会差不少。Python 的str是不可变对象每一次都会生成一个新的字符串在100[leetcode]这种用例下会产生大量临时对象垃圾回收压力陡增。Java 的Stack类是Vector的子类自带同步机制单线程下共享不必要的锁开销。很多老手会把Stack换成ArrayDeque因为ArrayDeque的 push/pop 接口足够用且没有同步开销。这个细节在面试中提出来会显得你很有工程经验。C 版本一般不需要特别优化因为std::string的本身是原地扩容效率不错。如果你追求极致压栈时可以std::move(cur)而不是cur的拷贝避免深拷贝但要注意 move 之后cur变为空字符串后续不能再误用旧值。实际刷题场景中常规输入规模下移动语义带来的收益可以忽略更关键的是逻辑正确。4. 常见问题与调试实录4.1 三个最容易翻车的位置根据我改过的代码和辅导过的同学字符串解码翻车最频繁的位置集中在三个方面。第一数字解析不完整。12[a]输入中如果只读一个字符就处理那么第一次读到1、第二次读到2会被当成两个独立数字块结果完全错误。正确做法是遇到数字字符就不断num num * 10 digit直到遇到[才停止。这个 bug 的隐蔽之处在于只在10以内的数字上测试时代码看起来完全正常一旦出现两位数字就露馅。第二遇到[忘记清空cur。这是初学者最高频的错误。清空cur相当于“进入内层时重新开始累积文本”如果不做内层字符就会累积到外层字符串后面去。这个 bug 在单层嵌套时还好发现多层嵌套时会以非常诡异的方式显现让人难以定位。我的建议是把cur 写在压栈语句的正下方作为进入内层固定的三步之一“压入外层状态、重置次数、清空当前串”。第三]拼接顺序写反。正确顺序是“外层前缀在前当前层重复结果在后”。写成cur cur * k prevStr会让前缀跑到后面导致嵌套结构错位。我是靠手动走2[a2[b]]这类用例才发现这个顺序敏感性的。如果你也经常在这一步出错一定要在纸上多画几个括号层级。4.2 一个调试技巧打印栈状态当代码在处理某个用例时失败不要急着东改一行西改一行。最高效的排查方式是打印中间状态观察“入栈时压进的内容”和“出栈时弹出的内容”是否符合预期。以 C 为例可以在 push/pop 的节点加上条件打印cerr push: num num , cur[ cur ] endl;用 Python 可以在循环开头打一行print(fi{self.i}, ch{ch}, cur{cur}, stack_size{len(stack)})打印时重点关注两个检查点入栈时压入的prevStr是否就是“进入内层之前已经拼好的字符串”出栈时弹出的k和prevStr是否是和当前]匹配的最近一层状态。只要这两个值符合预期逻辑错误一般就定位得差不多。如果发现出栈弹出的不是最近层的状态大概率是栈的入栈时机写错了或者某一步多压了一次、漏压了一次。调试栈相关代码还有一个通用心得在本地测试时把一个复杂用例拆成多个简单用例逐个跑。比如先测3[a]再测3[a2[b]]最后才上3[z]2[2[y]pq4[2[jk]e1[f]]]。这样能快速区分是基础逻辑问题还是多层级联问题。4.3 复杂度分析为什么不是 O(n²)很多人在分析字符串解码的时间复杂度时会犹豫每个字符要读一遍遇到]时还要把当前字符串重复 k 次重复操作会不会导致二次方复杂度认真算一下会发现最终输出的字符串长度就是所有字符展开后的总长度。每次拼接操作的代价都正比于它实际生成的字符串长度所以所有拼接加起来的总代价是 O(S)其中 S 是最终展开字符串的长度。整个算法遍历输入字符串的代价是 O(n)而 n 小于等于 S因此整体复杂度可以写成 O(S)。这个 S 也是理论上的下界——你无法在少于输出长度的代价里完成输出。空间复杂度方面栈里保存的所有字符串长度加在一起也不会超过 S所以空间也是 O(S)。这里有一个工程上要留意的点复杂度公式里的 O(S) 说的是“必然要付出的输出代价”但不同写法的常数差异很大。Python 里如果大量使用不可变字符串拼接虽然渐进复杂度同样是 O(S)实际运行时间可能比用列表拼接慢好几倍。换句话说这道题即使复杂度达标性能仍然可能与实现细节强相关。刷题时你可以在超长用例上对比一下“cur ”和“list.append加join”两种写法的耗时体感会非常明显。5. 从题目到工程字符串解码的延伸价值5.1 模板引擎里的展开逻辑k[encoded_string]这种规则其实是不少模板引擎和配置系统的简化版。真实的模板引擎会有变量插值、条件判断、循环展开等更复杂的能力但底层解析嵌套结构的方式和字符串解码完全同源遇到标识符进入下一层遇到结束符回到上一层用栈或递归管理已经收集的片段。举一个我实际见过的场景某团队需要批量生成测试数据他们有一个模板长这样3[user_2[case]]需要展开成“user 用例”的固定组合。如果用朴素逻辑手写循环每一层都要维护计数器和偏移量非常容易错。后来有人发现这就是字符串解码的原型直接套用栈方案改了一个解析函数几分钟就把整个流程跑通了。类似的需求还有很多生成重复配置项、批量构造测试账号、填充报表模板的重复分组等等。只要你在工程中见到数字[内容]这种格式脑子里就该冒出字符串解码这道题。5.2 嵌套文本解析的通用心智模型字符串解码培养的“嵌套状态管理”能力可以平移到很多看起来不相关的场景。HTML 标签解析、XML 节点层级、JSON 对象嵌套、Markdown 加粗语法、表达式括号匹配、AST 构建……它们本质上都是同一棵技能树上的分支一个 tokenizer 负责把输入切成有意义的片段一个栈或递归负责维护嵌套层级一个 builder 负责在合适的时候产出结果。我在带新人时会把字符串解码作为“解析器入门”的第一道推荐题。新人把它吃透之后再去看 JSON 解析器源码普遍反馈是“原来 token 和栈的东西并没有那么高深”。这种从一道题延伸到一系列问题的认知升级往往比多刷十道题更有价值。掌握了这种心智模型之后你再遇到一个陌生格式第一反应就不再是“这个格式好难”而是“我先分清楚它的 token 有哪些、嵌套规则是什么、什么时候该入栈、什么时候该出栈”。这套分析框架是通用的。5.3 刷题之外的沉淀从一道题到一类能力如果把刷题的目标定位成“AC 了事”那收获的只是会做一道题但如果你愿意多花一个小时把这道题的栈版本、递归版本、测试矩阵、复杂度推导全部走一遍收获的是一种能解决嵌套解析问题的通用能力。我个人在复盘时习惯做三件事写完一种解法后再写第二种解法比较两种解法的差异把代码删掉隔一天重新手写一遍检验是否真的理解了把这道题的思路口头讲给别人听讲得清楚的才是真掌握。字符串解码是一个绝佳的复盘样例因为它足够经典、解法多样、边界丰富能同时锻炼栈、递归、字符串处理和测试设计。如果你最近在准备面试我建议把它列入必练清单并且至少在纸上手写三遍以上。等你练到看到任意嵌套字符串都能在五秒内反应出“遇[压栈、遇]出栈”的状态变化时这一类题目在你眼里就再也没有秘密了。最后再分享一个小经验不要害怕在面试过程中手动模拟一个用例。当你不确定自己的代码在某个嵌套用例上的行为时主动说“我可以走一个例子验证一下思路”并用笔在纸上画出栈的变化这比沉默地改代码更能让面试官认可你的解题思维。字符串解码这道题的价值也正在于此——它考察的从来不只是你会不会写代码而是你能不能把一个复杂嵌套的过程讲得清清楚楚、写得明明白白。