有些算法题你第一眼觉得它就这等到真正落笔写代码才发现坑一个接一个往外冒。字符串解码LeetCode 394就是这么一道典型的题目题面简单到只有一句给定一个编码字符串返回解码结果规则也清清楚楚——k[encoded_string]表示方括号里的内容重复 k 次。可真到了面试或者实际工程里多位数、多层嵌套、空串、拼接顺序、栈里到底该存什么……每一个小细节都可能让提交从通过变成不通过。这篇文章不打算只贴一份标准答案。我想把这道题当作一个完整的重复展开问题来拆解从解码规则怎么读、为什么栈是天然解到双栈方案的完整推导、递归写法的对照再复盘我实际提交时踩过的各种边界问题最后聊聊这类解码逻辑在压缩日志、协议解析、模板渲染里是怎么变形的。不管你是刚开始刷题的新手还是想把算法思维迁移到业务代码里的工程师这套思路应该都能直接拿过去用。1. 拿到题先别急着写代码把解码规则彻底读透1.1 编码规则的本质方括号重复展开题目给的编码格式是k[encoded_string]其中k是重复次数方括号里面是待展开的字符串。简单来说3[a]就是aaa2[bc]就是bcbc。但注意规则说的是encoded_string它本身又可以是带方括号的编码串所以3[a2[c]]这种嵌套形式是合法输入要先算内层2[c] cc再把结果放进外层乘三倍最终得到accaccacc。这背后其实是典型的递归结构定义一个表达式可以展开成一个子表达式子表达式里又嵌套着另一个子表达式。这种结构和 XML 标签嵌套、编程语言里的括号块、数学公式里的括号运算是一模一样的。换句话说这道题真正想考察的不是你会不会用某个 API而是你对嵌套结构的顺序处理有没有清晰的解法。另一个容易被忽略的点是拼接顺序编码串可以包含普通字符、数字和括号的任意组合。2[abc]3[cd]ef这种例子结果是abcabccdcdcdef也就是说普通字符ef跟在前面展开的结果后面顺序不能乱。顺序性在嵌套场景里尤其敏感我见过很多人在3[a2[c]]这种例子上栽跟头就是因为把外层字符串和内层展开结果拼错位置。1.2 数字、括号、字母三类字符的职责边界整个字符串里只有三类角色搞清楚它们各自的职责实现时就不会乱数字字符它只负责告诉我们要重复几次并且有可能出现多位数例如12[a]表示a重复 12 次而不是先重复 1 次再重复 2 次。左括号[它标志着一个重复单元的开始。遇到它时前面累计好的数字就是当前单元的重复次数而进入这个单元后需要重新累计内部字符串。右括号]它标志着一个重复单元的结束这时要做一次真正的解码操作取出最近的重复次数结合括号内已经收集到的子串生成展开后的字符串。普通字母直接追加进当前位置正在累积的结果里不参与任何运算。把这个三类角色的关系理顺之后你自然会想到一个关键问题右括号出现时我怎么找到最近的左括号和它对应的数字这个最近匹配的语义恰恰是栈的用武之地。这也是为什么网上几乎所有解法都绕不开栈——它不是解题技巧而是这个问题本身的结构使然。2. 为什么栈天然适配这种解码逻辑2.1 从最近的左括号反推栈的行为假设你正在解析字符串一路上不断把普通字母拼到当前结果里。突然遇到一个右括号你首先需要回退到最近的那个左括号然后把这一段封闭区间里的字符串重复指定次数再拼回它前面的外层结果中去。这个一层一层展开、展开完再回到上一层的过程和函数调用的嵌套返回非常像也和浏览器解析 HTML 标签时的压栈弹栈一模一样。只要遇到[就压栈遇到]就弹栈就能保证每次弹出来的东西一定是最近的那个未闭合左括号对应的内容。这就是后进先出LIFO最直观的体现。我早期学这道题时也曾尝试用一个全局指针配合递归去模拟回溯写出来也能跑。但递归本质上也是系统在帮你维护调用栈跟手写栈殊途同归。真要说区别手写栈更显式出问题更容易调试递归更简洁但嵌套很深时容易把调用栈打爆。两种方案在后面的章节我都会展开。2.2 双栈和单栈两种实现路线的取舍栈方案里最核心的设计决策是栈里存什么比较常见的做法是双栈一个数字栈存的是每个重复单元的k一个字符串栈存的是每个括号单元开口之前已经积累好的外层字符串。我比较推荐这种方式因为逻辑最直白变量职责单一面试时讲起来也最不容易绕晕。单栈方案也有不少实现比如把数字 左括号 字符串整体作为一个待处理单元压进栈里甚至用一个栈交替存储数字、字符串、操作符之类的东西。单栈节约了一点内存但代码可读性会明显下降状态判断也更复杂。我在工程实践中不太推荐为了省那点空间牺牲调试的便利性尤其是这类题目本身空间复杂度就是 O(n)双栈并不会改变量级。还有一类思路是用两个队列或者先递归展开再拼接的做法本质上都是把暂停当前上下文这个动作换了一种写法。面试时提一句可以但实现上我建议还是紧扣双栈因为它的每一步操作都很规整不容易出现索引错位的问题。3. 手写实现双栈方案一步步推敲3.1 主循环的状态机拆解双栈解法的核心就是一个循环遍历字符串每个字符按前一章的三类角色分支处理。我们用两个栈再加上两个临时变量cur_num负责累计当前单元的数字cur_str负责累计当前正在拼接的字符串。每来一个字符处理的逻辑如下是数字累加到cur_num注意要cur_num cur_num * 10 int(ch)这样才能处理多位数。是[说明前面积累的cur_num和cur_str都属于外层上下文把它们分别压入数字栈和字符串栈然后清空cur_num和cur_str开始处理方括号内的新上下文。是]从数字栈弹出重复次数k从字符串栈弹出进入这个括号之前的外层字符串prev_str然后执行cur_str prev_str cur_str * k。注意这里必须是prev_str在前、展开结果在后因为括号单元是嵌套在外层字符串内部的。是普通字母直接cur_str ch。循环结束后cur_str就是最终解码结果直接返回即可。这个流程之所以稳定是因为它保证了一个不变量在任何时刻cur_str保存的都是当前这一层括号内已经解析好的内容而两个栈分别保存着所有外层上下文的数字和字符串。3.2 这段代码最容易写错的两个地方第一个高发错误点是]分支里的拼接顺序。很多人会写成cur_str cur_str * k prev_str这样就把外层字符串放到了展开结果后面结果整个顺序颠倒。实际上prev_str是在[之前就已经存在的字符串而cur_str是这一层括号内的内容展开之后应该嵌在prev_str的后面所以必须是prev_str cur_str * k。第二个高发错误点是数字累加。如果字符串里只有一个一位数那不累加也不会出错可一旦出现12[a]如果你用的是num int(ch)得到的就是1[a]和2[a]分开处理完全错误。解决办法就是永远别假设数字只有一位用cur_num cur_num * 10 int(ch)把前面的十位、百位正确衔接上。还有一个小细节LeetCode 的输入保证格式合法但在真实业务里输入往往不合法。这时候我建议在解析前加一个简单的校验逻辑至少检查括号是否配对、数字是否溢出之类的状况。别把侥幸当约定工程代码永远要假设输入是恶意的。3.3 完整实现与复杂度说明下面是完整的 Python 实现每一行的意图我都用注释标注了出来。def decodeString(s: str) - str: num_stack [] # 保存每一层外层上下文的重复次数 str_stack [] # 保存每一层外层上下文已拼接的字符串 cur_num 0 cur_str for ch in s: if ch.isdigit(): # 多位数累加例如 12 - 1 - 1*102 12 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时间复杂度是 O(n)n 是最终输出字符串的长度。如果你只用输出长度来估算可能会觉得不够准确因为cur_str * repeat_times这一步会一次性生成很长的中间字符串但总体上看每个字符最多被复制和拼接常数次量级仍然是 O(n)。空间复杂度也是 O(n)两个栈各占一部分可能达到输出串大小量级。我实际提交过这版代码边界样例全部通过跑 LeetCode 上那批大字符串用例也很快。相比后面要讲的递归版本这个写法最大的优势是不依赖系统调用栈不会因为嵌套层数过深而栈溢出同时所有状态都显式保存在变量里打印日志排查时非常直观。4. 递归解法把嵌套交给调用栈4.1 索引下标接力的递归写法递归解法的思路和栈解法其实同源只是我们不再手动维护两个栈而是让函数调用的嵌套天然形成上下文栈。不过这里有个关键设计递归函数必须返回两个值——一个是解析出来的子串另一个是当前解析到了原字符串的哪个位置。这是因为递归时如果只传子串函数内部很难知道外层该从哪里继续读。很多新手写递归版失败都是因为忽略了下标同步这件事。def decodeString(s: str) - str: def dfs(pos: int): result [] num 0 while pos len(s): ch s[pos] if ch.isdigit(): num num * 10 int(ch) pos 1 elif ch [: # 递归解析括号内的子串并拿到新的下标 inner, pos dfs(pos 1) result.append(inner * num) num 0 elif ch ]: # 当前层解析结束返回结果和新下标 return .join(result), pos 1 else: result.append(ch) pos 1 return .join(result), pos return dfs(0)[0]这段代码的精髓在于遇到[时不做拼接而是递归进入下一层遇到]时返回本层结果同时把pos推进到右括号的下一位外层函数就从这个位置继续解析。整个过程的栈由函数调用栈天然承担逻辑上非常接近编译原理里的递归下降解析器读起来结构清晰面试讲解时也容易让人理解。4.2 递归与栈的性能对比和实际选择从理论上说递归版本的时间复杂度和空间复杂度跟栈版本一样都是 O(n)常数因子也不会差太多。但在实际工程和面试场景里两者还是有明显区别维度双栈迭代递归 下标可读性状态机直观但分支略多结构贴近语法树容易理解调试难度变量都在明处容易打日志依赖调用栈深层次错误定位麻烦栈溢出风险低只用了显式栈高嵌套深度等于递归深度实现复杂度中等中等偏低我个人在面试时建议先用递归版本讲清思路因为它最快能让人理解嵌套展开这个本质但写代码时如果面试官没有特别要求我会更推荐双栈版本毕竟它不会因为极端用例触发栈溢出。实际工作中解析模板嵌套或者协议数据时我更倾向于把递归写法压成迭代原因很现实生产环境的输入长度不可控一个不小心就会让调用栈爆掉。5. 踩坑复盘那些提交前胸有成竹、交上去就沉默的边界5.1 多位数累加从1到12的事故现场我第一次写这题时天真地用int(ch)直接处理数字字符结果跑12[a]只返回了1a而不是aaaaaaaaaaaa。原因是数字字符在字符串里一个接一个出现但左括号只有一个必须把连续的多个数字字符合并成一个整数。正确的思考方式是数字字符是分多次读入的但真正使用数字的时刻是遇到左括号时。所以必须有一个半成品变量持续累加。这类问题在解析场景里太常见了从 XML 属性值的数字解析到网络报文里读取长度字段都是同样的套路先累积整数遇到分隔符再消费。给个自查方法凡是你的代码里出现int(cur_char)且没有乘 10 的步骤就要警惕多位数输入。最好写个测试先测10[a]再测100[a]直接暴露问题。5.2 空括号、空字符串与栈空问题有些实现会在]分支直接访问栈顶如果遇到3[]这种输入或者某些不合法的空括号就可能在错误的地方触发索引异常。LeetCode 的测试数据里未必有空括号但真实业务里用户输入可不会这么客气。更隐蔽的是初始空串问题最外层开始解析时cur_str是空串但千万别在]分支里错误地判断当前字符串为空就直接跳过展开因为空串也可能是合法结果。栈解法对空串没有任何特殊处理恰恰说明它更稳。如果你在处理时会遇到栈空的情况往往不是空串导致的而是输入本身括号不配对。生产环境中至少应该加一层合法性校验避免程序直接崩溃。5.3 拼接顺序是先乘再拼还是先拼再乘这是这道题最经典的一个顺序坑。以2[a3[b]]为例我们期望的过程是内层3[b]展开成bbb拼上外层a得到abbb再整体重复两次得到abbbabbb。如果代码写成cur_str cur_str * k prev_str你就会得到bbbabbbabbb之类的乱序结果。我在多个交流群里看到过有人问为什么我的输出是反的问题几乎都出现在这里。记忆的方法也很简单左括号出现时保存的是这段内容之前的字符串右括号出现时当前cur_str是这段内容本身我们做的操作是把这段话展开后接在之前那段之后。一句话概括就是先把展开结果算好再往后面的位置放。5.4 嵌套三层以上时的回退位置错误递归版本里一个很容易忽略的点是dfs(pos 1)返回后的pos更新。如果写递归时漏掉让内部函数把pos带出来外层就会从错误的位置继续解析典型表现是单层嵌套正确两层嵌套错一半三层嵌套基本全乱。栈版本相对不容易犯这个错因为它的下标推进是天然的循环for ch in s不需要手动管理位置。但在处理3[a2[c]]这类输入时我还是建议在纸上手动模拟一遍栈的变化过程把每个[和]对应的压栈、弹栈动作都标清楚。这个过程对理解整道题的上下文切换非常有帮助。6. 从 LeetCode 394 到生产环境解码思路的真实变形6.1 协议解析和日志还原里的同款逻辑字符串解码的重复展开模式在真实工程里远比想象中常见。举几个例子某些自研日志格式为了降低存储占用会把连续重复的片段编码成N:pattern的形式读取日志时就要像本题一样先解析数字再展开内容。网络协议里常见的 TLV类型-长度-值结构本质上就是先读长度再按长度取数据这和k[encoded_string]的顺序完全一致。ZIP 等压缩算法中的 LZ77、BWTMTF 等方案虽然原理复杂得多但把前面出现过的片段重复展开这个思路跟3[a]的展开思想一脉相承。所以不要觉得 LeetCode 题和真实工作离得远。你写的每一个解析器只要涉及到嵌套结构 重复次数 拼接顺序几乎都可以套用这道题的状态机模型。6.2 模板引擎和 DSL 表达式的嵌套展开模板语言里最常见的就是循环渲染比如{{#times 3}}hello{{/times}}这种形式。它和这题的区别是模板引擎通常还要支持条件判断、变量替换、多层嵌套的复杂语义但核心的遇到起始标记 - 解析内部内容 - 遇到结束标记 - 回退外层流程一模一样。如果你已经熟练掌握双栈解法再去看 Handlebars、Mustache、Vue 模板编译器的源码会发现自己能很快理解它们维护的那一堆上下文栈到底在干什么。反过来如果你在工作中写过模板引擎的解析器再回来做这道题几乎不用想就能写出正确代码。这里有一个更进阶的变形版本把k换成变量名把[ ]换成自定义标签就变成了一个迷你 DSL 解释器。我建议有兴趣的读者可以尝试实现一个{name:times}[content]的解析器解完这道题再扩展一下成就感会很强。6.3 一个工程建议先画状态迁移表再动手写代码最后分享一个我在实际开发中反复验证过的经验遇到任何字符串解析类问题先别急着写循环先把状态迁移表画出来。以本题为例状态迁移表可以简化为当前字符当前状态动作数字累积数字cur_num cur_num * 10 int(ch)[进入子层压栈清空临时变量]退出子层弹栈拼接展开串字母累积字符串cur_str ch这张表不仅写代码时能帮你理清逻辑分支debug 时也能帮你快速定位某个字符触发了错误分支的问题。我见过很多同事代码写得很乱一问原因都是没想清楚状态就直接上循环出了 bug 只能靠 print 硬试。养成先梳理状态再编码的习惯可以少走非常多的弯路。我在实际处理这类嵌套展开问题时还有一个习惯先跑通小样例3[a]2[bc]再跑通嵌套样例3[a2[c]]最后专门准备一组长输入和多位数用例如12[a]30[b2[c]]做压力验证。这三个层次的用例覆盖住基本就能保证这道题在绝大多数输入下不会翻车。