看到3[a2[bc]]这种字符串时很多人第一反应是找对称括号然后手算出结果。但字符串解码这道题真正要训练的不是“肉眼观察对称”而是让你像一台解析器一样逐字消费输入把数字、方括号、普通字母当作三类信号来处理。字符串解码可以说是算法题里的一棵常青树也是从“会写栈”到“理解状态机”的一个分水岭它看起来只是重复拼接但一旦出现多层嵌套没有清晰的“保存现场/恢复现场”思维代码很快就会乱成一团。这篇文章会把字符串解码的两种主流解法——双栈迭代法和递归DFS法——完整拆开包括为什么需要两个栈、递归函数里的索引为什么要用返回值传递、多位数字怎么累加、拼接顺序为什么不能反以及我实际调试时踩过的几个坑。无论你是刚开始刷题的新手还是想把这题讲给别人听的面试准备者这篇文章都值得看完。我会把每一步的“为什么”也解释清楚而不是丢一个能过的代码就完事。1. 不要急着写代码先把题目规则和嵌套直觉建立起来1.1 编码规则到底在说什么题目给出的规则用一个模式就能概括k[encoded_string]表示方括号内部的字符串重复 k 次其中 k 是一个正整数。这里的encoded_string不一定是普通字母串它还可以继续包含新的k[encoded_string]也就是可以嵌套。举几个最直观的例子3[a]2[bc]解码成aaabcbc3[a2[c]]解码成accaccacc2[abc]3[cd]ef解码成abcabccdcdcdefabc3[cd]xyz解码成abccdcdcdxyz注意最后两个例子方括号前面或后面可以有普通字母。这些“光秃秃”的字母不属于任何重复块它们必须原样保留并且位置的先后顺序不能变。也就是说真正被“解码”的单元是k[...]这个整体其他字符都是普通字面量。还有一个容易忽略的点题目一般会保证所有括号都是合法配对的也就是不会出现[a]b[c这种残缺输入。但是如果实际项目里要解析用户生成的模板括号配对这个假设就不一定成立了。因此写代码前确认输入约束是一件很重要的事后面我会专门讲。1.2 方括号嵌套天然对应“栈”和“递归”3[a2[c]]这种结构如果用手工展开你会不自觉地先处理内层先看最内层2[c]得到cc然后把结果放回上一层a cc变成3[acc]最后再乘以 3得到accaccacc这个“从内向外”的处理顺序和栈的后进先出特性完全一致。最内层的括号最后进入却最先被解析外层括号先进入最后才被结算。换句话说方括号的嵌套深度有多少层解析时就需要记住多少层“尚未完成的上下文”。这里可以用俄罗斯套娃来类比最外层的套娃要先打开但最里层的小套娃是最先被看见的。当你打开一个套娃时你暂时放下了外面的那一层等你把里面的套娃处理完又会回来继续组装外层的部分。在代码里这个“暂时放下”就是入栈“回来组装”就是出栈。同样地递归也很自然地匹配这个结构每当遇到[就调用一个新函数去解析更内层的块内层解析完返回结果外层再继续。函数调用栈本身就是替你保存上下文的容器所以递归解法可以不用手写栈。理解这两种思路是吃透字符串解码的关键。2. 双栈迭代解法分开放置“重复次数”和“上层字符串”2.1 为什么一个栈不够很多人刚开始会想这不就是括号匹配吗我只要用一个栈遇到]就弹出来拼接。但这道题和纯括号匹配有一个重要区别每个括号块除了需要弹出一段字符串还必须知道自己被重复了多少次。如果你只用一个栈那栈里既要放字符串又要放数字。pop 出来的时候你怎么知道弹出来的是数字还是字符串虽然可以用元组把两者打包放进去但手动维护起来变数很多出错的概率也更高。更合理的做法是用两个栈数字栈count_stack保存每一层方括号前面的重复次数。字符串栈str_stack保存进入当前方括号之前已经拼好的那一部分结果。为什么要这么拆本质原因是处理嵌套时有两个独立维度的状态需要保存一个是“这一层当前重复多少次”另一个是“外层之前已经构造到什么程度”。它们会同时变化也同时被需要所以干脆分开存让每个栈的职责单一。我的理解方式是每当遇到一个[就等于对当前的解析过程喊了一声“暂停”把当前的重复次数和字符串前缀保存起来然后去处理内部的内容每当遇到一个]就是从最内层返回上一层弹出之前保存的上下文把这一层的结果合并进去。2.2 遍历过程中每个字符的三种处理逻辑双栈解法的核心就是维护两个变量cur_num表示当前连续读到的数字cur_str表示当前层已经累积的字符串。扫描字符串的每一个字符分四种情况处理数字累加到cur_num上。注意数字可能是多位比如12[a]所以要用cur_num cur_num * 10 int(ch)。字母追加到cur_str。这里不用管它属于哪一层因为在当前扫描状态下我们本来就是在“当前层”累积字符。[准备进入新的一层。先把cur_num压入数字栈把cur_str压入字符串栈然后重置cur_num 0、cur_str 。]当前层结束。从数字栈弹出重复次数count从字符串栈弹出上一层的字符串prev_str然后拼接cur_str prev_str cur_str * count。这个逻辑写成 Python 代码非常短def decode_string(s: str) - str: count_stack [] str_stack [] cur_num 0 cur_str for ch in s: if ch.isdigit(): cur_num cur_num * 10 int(ch) elif ch [: count_stack.append(cur_num) str_stack.append(cur_str) cur_num 0 cur_str elif ch ]: repeat_count count_stack.pop() prev_str str_stack.pop() cur_str prev_str cur_str * repeat_count else: cur_str ch return cur_str很多初学者看不懂为什么遇到[要把cur_str重置为空。其实这不是丢掉已有结果而是因为字符串栈已经把之前的cur_str保存好了。重置为空是为了让这个变量能用来累积“当前这一层”的内容。等遇到]时再把它和之前的cur_str拼接起来。cur_str prev_str cur_str * repeat_count这一行的顺序也很关键。prev_str是外层已经构造好的内容它必须在前cur_str是刚刚解析完的括号块内容它在后。如果顺序反了比如先拼接cur_str * count再加prev_str那整个字符串的顺序就全错了。2.3 手动走一遍2[a3[bc]]建立“保存现场”的直觉拿一个带嵌套的例子来手推这样比只看代码更有体感。输入2[a3[bc]]期望输出是abcbcabcbc过程如下当前字符cur_numcur_str数字栈字符串栈动作说明初始0[][]开始22[][]累积数字[0[2][]保存外层状态并清零a0a[2][]普通字母拼入当前层33a[2][]累积数字[0[2, 3][, a]再次保存当前状态并清零b0b[2, 3][, a]拼入内层c0bc[2, 3][, a]拼入内层]0abcbc[2][]弹出次数3和前缀aa bc*3]0abcbcabcbc[][]弹出次数2和空串空串 abcbc*2这个表格值得自己走一遍感受一下。每次出现[cur_num和cur_str都被重置但重置前的最外层状态已经被妥善保存在栈里。等遇到]再从栈里取回来。这样循环往复嵌套多少层都不怕。如果只看最终代码这题很短很优雅但实际面试或实践中最容易出问题的恰恰是“重置”这一步。之所以要把这两个变量压进栈再清零是因为解析器的本质是一个“逐层推进”的过程每一层的状态之间互不干扰只有在层结束的那一刻才需要合并。3. 递归DFS解法让函数调用栈替你想事情3.1 递归与嵌套结构的天然对应双栈解法需要你手动管理“暂停/恢复”而递归解法把这个负担交给了函数调用栈。思路非常直接写一个递归函数dfs(s, i)它从位置i开始解析一个编码块返回两个值——解析出来的字符串以及解析结束后下一个要处理的下标。为什么需要返回下标因为字符串是一个顺序结构递归进入内层解析后必须知道内层主体结束的]在哪里外层才能从正确的位置继续往下读。如果用全局变量保存下标一旦递归嵌套全局变量在层层调用之间互相覆盖结果会非常混乱。用返回值传递下标是教科书里处理字符串递归解析的标准做法这里也一样。3.2 递归函数的三个分支代码可以这样写def decode_string_recursive(s: str): def dfs(i: int): res [] num 0 while i len(s): ch s[i] if ch.isdigit(): num num * 10 int(ch) i 1 elif ch [: i 1 sub_str, i dfs(i) res.append(sub_str * num) num 0 elif ch ]: i 1 return .join(res), i else: res.append(ch) i 1 return .join(res), i return dfs(0)[0]这个函数内部分三个关键分支数字分支和双栈解法一样用num num * 10 int(ch)处理多位数字。[分支这是递归的核心。先让下标加 1跳过左括号然后递归调用dfs(i)。递归返回时我们得到了内层解析出的字符串sub_str和新的下标i。此时把sub_str * num加到结果列表里。这里有个重要的细节num需要重置为 0否则下一个数字块会继续使用上一个块的重复次数。]分支说明当前这一层已经结束直接返回当前拼接好的字符串和i 1跳过右括号。为什么这里把字符收集在res列表里而不是直接拼接字符串因为 Python 字符串是不可变对象频繁在深层循环里会有额外开销。用列表收集最后.join(res)一次成型是一个更稳的习惯。当然对于这道题的规模直接拼字符串也能过只是代码洁癖问题。3.3 双栈和递归的对比什么时候选哪个两种解法都能做到时间复杂度和空间复杂度相近但实际使用时有很多微妙差异。用一个表格对比更清晰维度双栈迭代递归DFS上下文保存方式显式数字栈 字符串栈函数调用栈隐式保存理解门槛需要理解“保存现场/恢复现场”更贴近手工展开的直觉嵌套深度风险无栈溢出风险迭代可控递归深度受语言限制嵌套过深可能爆栈代码长度较短但状态变量多较短但需要理解返回值传递下标推荐场景面试实现、工程代码、解析器思路讲解、原型验证、口头描述我个人在面试里讲这道题时会先用递归解释嵌套逻辑因为它的思路最贴近人脑然后实现时写成双栈迭代因为它在极端输入下更稳定也不会被递归深度卡住。两者的代码量其实差不多掌握一个另一个也能顺手写出来。4. 最容易踩的坑与一套可复现的自测用例4.1 多位数字的累积与重置一对孪生陷阱第一个常见的坑是数字累加起来不对。比如输入12[a]如果只写cur_num int(ch)而不是cur_num cur_num * 10 int(ch)那12会被读成1和2两个独立的数字结果变成a重复 2 次而不是 12 次。第二个常见的坑是重置时机不对。有人会在遇到[时压栈但不把cur_num清零。这样处理完一个嵌套块后cur_num还保留着上一个块的重复次数遇到下一个[时新的次数会在这个陈旧值基础上继续累加导致结果完全错乱。这两个坑往往同时出现。建议在写代码时自查一遍cur_num什么时候清零答案是有且只有两个时机——遇到[压栈后、遇到]弹栈结算后。其他时候cur_num要么在累积数字要么保持不动。4.2 拼接顺序为什么prev_str必须在左边还有一类错误是把拼接写反。错误版本长这样cur_str cur_str * repeat_count prev_str这行代码会把括号块的内容放到外层内容的前面。比如输入a2[b]正确结果是abb但这个错误版本会算出bba。原因很直接我们在解析过程中prev_str代表的是“进入当前括号之前已经存在的内容”它一定是当前块的前缀不可能出现在后面。另外cur_str * repeat_count和repeat_count * cur_str在 Python 里结果一致因为乘法满足交换律所以这一部分顺序写反不影响结果。真正影响结果的是prev_str和cur_str * repeat_count两者的左右位置。这个顺序问题在递归解法里同样存在递归拼接时也要注意把内层解析结果追加在外层结果的右边。4.3 自测用例清单覆盖空串、多位数字、嵌套、前后缀一道题写完提交前我会习惯性跑一组用例覆盖这几个最容易出事的边界。下面是我会用的清单输入期望输出用来验证什么空字符串边界abcabc无括号原样返回3[a]aaa最基础的重复3[a2[c]]accaccacc多层嵌套2[abc]3[cd]efabcabccdcdcdef多个块 普通前缀/后缀12[a]aaaaaaaaaaaa多位数字a[b]cabc次数是1需要结合具体题目确认100[a]a * 100大重复次数最后一个用例顺便能测出语言字符串乘法的性能表现尤其是 Python 里a * 100是很自然的写法不用担心。但如果某个语言对大次数乘法有特殊语义务必先测试。5. 从字符串解码到真正的解析器一种可迁移的思维模型5.1 把题目理解为“带状态的字符流扫描”字符串解码并不只是一个独立的算法题。当你把它拆开看它其实是一个极简的文本解析器输入是字符流输出是展开后的字符串中间靠cur_num和cur_str两个状态变量来记录解析进度遇到[暂停当前状态遇到]恢复并结算。这种“状态变量 栈”的组合在真实工程中非常常见模板引擎解析{{ variable }}时需要找到变量边界。JSON 解析器遇到{[时需要维护对象嵌套层级。配置文件解析器处理key value时需要记录当前段名。文件系统路径解析要处理.、..和符号链接。所有这些场景的核心逻辑都和字符串解码一样逐字符扫描遇到某种边界符号就改变状态或压栈结束边界就弹栈合并。理解这道题相当于理解了这一类解析问题的最小范式。5.2 同类变体从单层重复到笛卡尔积展开字符串解码还有不少变体掌握基础解法后可以顺带想一想。比如有的变体会把方括号里的内容变成2[a,b]要求展开成a,ba,b也就是每个元素都要重复 2 次中间保留分隔符。这种题的双栈解法骨架完全一样差别只在于弹栈后不是简单拼接字符串而是要对一组元素做循环展开。再比如有的变体和计算器结合像3[a]2[b]要求先按加法规则分段每段分别解码再合并。这种题的本质是给字符串解码叠加一层运算优先级而优先级本身又可以用栈或递归来解决。思路都是一脉相承的识别嵌套边界用栈保存上下文在合适的时机合并结果。遇到变体题时先想清楚“栈里存什么、什么时候压栈、什么时候弹栈、弹出来怎么合并”这四个问题答案就基本出来了。6. 面试和实战中的几个实操心得6.1 写代码前先确认三件事字符串解码的题目描述通常默认了几个条件但实际场景或面试追问时不一定完全一致。我会在写代码前主动确认k 是否一定是正整数如果是 00[a]应该输出空串代码要额外处理吗数字是否可能为多位如果题目没说明按照常规理解写成多位累积一定更安全。输入是否保证所有括号匹配且不交叉如果不保证要不要加异常检测其实在大多数在线评测里这些约束都是给定的。但如果是设计一个真实功能用户输入什么都有可能。提前确认一遍能避免写出“只能过题但经不起真实数据”的脆弱代码。六点二把双栈解法翻译成“保存现场/恢复现场”如果让我用一句话总结双栈解法那就是遇到[保存现场遇到]恢复现场。这句话不仅适用于这道题还适用于一大批“嵌套结构解析”的题。每次处理左括号就把当前上下文压栈重置当前状态每次处理右括号就弹出上下文把当前层的结果合并进去。这样的思维模型比死记代码更容易迁移遇到类似题目时也能快速搭出框架。6.3 我第一次写这套代码时踩的坑最后分享一点实际经历。我最初写这道题时用的是一个单一的列表试图通过判断元素类型来区分数字和字符串。结果嵌套多了之后pop 出来的元素既要判断isinstance还要处理各种边界顺序代码变得又长又丑而且 debug 起来非常痛苦。后来改成双栈思路一下清晰了代码也短了一半。另一次让我印象比较深的失误发生在重置上我把cur_str的重置写成了cur_num的重置结果输入2[a]时第一次]正常输出第二次处理却直接用上了上一次残留的cur_str。那次 debug 花了不少时间最后才发现是重置错了变量。从那以后我再写这类代码都会刻意检查“压栈后的清零”和“弹栈前的取值”是否一一对应。字符串解码本身不难但它背后的解析思维在真实场景里复现率很高。双栈迭代法和递归DFS法一个偏工程、一个偏原理两个都掌握之后再看各种带括号嵌套的题目都会有一种“不过如此”的感觉。如果你现在写这道题还不顺手不用急先按这篇文章里的表格手动走一遍2[a3[bc]]的过程再把代码自己敲一遍很快就能建立起手感。