1. 这道题为什么让这么多人在hot100里卡住1.1 题目到底在说什么力扣394题“字符串解码”在hot100里算是一道非常典型的“栈”应用题目但也是很多人在第一次接触时容易绕晕的题目。它的核心描述其实很短给定一个编码后的字符串比如3[a]2[bc]要你把它还原成aaabcbc。编码规则只有一条k[encoded_string]表示方括号内的字符串要重复 k 次k 保证是正整数。看起来很简单对吧但这里真正让人头疼的不是单层重复而是嵌套。比如3[a2[c]]你需要先算出a2[c]里的2[c]是cc然后整体变成acc最后再重复3遍得到accaccacc。一旦嵌套层数多起来顺序就很关键是先从内层开始还是先处理外层如果处理顺序错了结果可能完全不对。我第一次遇到这题脑子里第一个反应是“这不就是正则里的展开吗”然后试图用字符串替换的循环去处理。结果写出来不仅慢而且遇到嵌套就出bug。后来冷静下来分析才发现这题其实考的是“什么时候记住状态、什么时候恢复状态”也就是典型的栈场景。1.2 第一眼看上去的陷阱只盯着括号看是不行的很多人一开始的思路是遇到]就往回找匹配的[把里面的字符串取出来重复然后再拼回去。这个思路在单层嵌套下是通的但遇到3[a2[c]]这类多层嵌套操作起来非常痛苦你要反复在字符串里定位左括号、右括号还要自己处理数字可能多位的情况。而且每一轮替换后字符串长度会变原来的索引全部失效代码越写越复杂。我不止一次在评论区看到有人贴这种“暴力替换”的解法最后都是上千毫秒跑完内存也高得离谱。说白了这种思路本质上是对字符串做了大量的重复重建时间复杂度是 O(n^k) 级别的遇到深层嵌套直接爆炸。真正应该考虑的是如何在遍历一次字符串的过程中把需要重复的内容和需要重复的次数层层“暂存”起来等遇到]时再一次性展开。这种“暂存以后再用”的模式正好就是栈的天然应用场景。所以这道题的解法不在于你会不会调用系统栈而在于你愿不愿意用一个显式的栈来维护“待拼接的字符串”和“待使用的重复次数”。2. 从嵌套结构直击核心栈解法及其每一步的模拟2.1 为什么栈是首选它天然匹配括号的递归结构栈解决这个问题的本质是它可以把“外层字符串当时的进度”先压进去然后专心处理内层括号的内容等内层括号处理完再把结果弹出来和外层进度拼接。这种“遇到左边界保存现场遇到右边界恢复现场”的模式和函数递归调用完全一致——唯一的区别是递归使用的是系统栈而这里我们用一个显式的栈来存放状态。具体来说我们需要两个栈一个存放字符串一个存放数字。也可以只用一个栈把两者打包成对象压进去但为了代码清晰工程上一般分开写。当然你也可以用数组模拟栈效果一样。关键点在于入栈的时机不是遇到数字的时候而是遇到[的时候。因为[才是“内层开始”的明确信号。数字只是告诉我们要重复几次但在[出现之前我们还不知道要重复的内容是什么。我给一个经验性的总结遇到数字解析出完整数字遇到字母追加到当前字符串遇到[把当前字符串和数字入栈并重置它们遇到]弹出数字和之前的字符串把当前字符串重复后拼回去。就这样一条规则代码量极少。2.2 用3[a2[c]]完整走一遍入栈出栈过程很多人看题解觉得懂了自己写又出错原因是没真正在脑子里模拟过栈的变化。这里我把3[a2[c]]的每一步列出来大家跟着走一遍就懂了。初始状态curStr curNum 0两个栈均空。读到字符3解析数字curNum 3这里因为可能出现多位数字需要curNum curNum * 10 当前数字。读到字符[把curNum 3和curStr 压入栈然后重置curNum 0curStr 。读到字符a直接追加到当前字符串curStr a。读到字符2解析数字curNum 2。读到字符[把curNum 2和curStr a压入栈注意这里压入的是a而不是空字符串然后重置curNum 0curStr 。读到字符ccurStr c。读到字符]弹出栈顶数字2和栈顶字符串a。此时把当前curStr c重复 2 次变成cc然后拼接到弹出的a后面得到acc。更新curStr acc。注意这里弹出的栈顶字符串是内层[之前已经累积的内容一定要用它作为前缀而不是用它的值覆盖curStr。读到字符]弹出栈顶数字3和栈顶字符串。当前curStr acc重复 3 次变成accaccacc拼到空字符串后仍然是accaccacc。最后返回curStr。整个过程我画成表格更直观当前字符操作curStrcurNum栈字符串数字3解析数字3空[入栈并重置0( , 3)a追加a0( , 3)2解析数字a2( , 3)[入栈并重置0( , 3), (a , 2)c追加c0( , 3), (a , 2)]弹出并展开acc0( , 3)]弹出并展开accaccacc0空看到这里你应该明白了所谓“字符串解码”不过是把一个嵌套表达式展开成一个线性字符串。栈在这里扮演的就是“记忆现场”的角色不需要递归调用也不需要反复定位括号。2.3 代码实现Java和Python各给一份写Java的时候要注意String的反复拼接会产生大量中间对象我建议使用StringBuilder或者DequeString来做拼接。下面是我在实际刷题时用得很顺手的写法public String decodeString(String s) { DequeInteger numStack new ArrayDeque(); DequeStringBuilder 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); cur new StringBuilder(); num 0; } else if (c ]) { int k numStack.pop(); StringBuilder prev strStack.pop(); for (int i 0; i k; i) { prev.append(cur); } cur prev; } else { cur.append(c); } } return cur.toString(); }Python的写法类似用列表当栈def decodeString(s: str) - str: num_stack [] str_stack [] cur num 0 for c in s: if c.isdigit(): num num * 10 int(c) elif c [: num_stack.append(num) str_stack.append(cur) cur num 0 elif c ]: k num_stack.pop() prev str_stack.pop() cur prev k * cur else: cur c return cur这里我特别想说一下Java版本里prev.append(cur)这一步。很多人第一次写会写成cur cur.repeat(k)然后不管prev直接拼接这就是bug的来源。因为prev是[之前已经生成好的外层字符串它必须作为前缀保留。比如a2[c]在遇到内层2[c]时a已经被压入栈等到]弹出时你要做的是把c重复后接到a后面而不是把a丢掉。3. 另一种思路递归下降解析理解本质后会发现“栈只是递归的等价写法”3.1 用递归处理嵌套代码甚至比栈更直观如果你学过编译原理里的“递归下降分析”再看这道题会非常亲切。编码字符串的语法其实可以写成这样S - 字母 | 数字[S]也就是说一个字符串要么是一段普通字母要么是一个数字后跟一个方括号包着的子表达式。遇到嵌套时无非是子表达式里又包含数字[子表达式]。所以我们可以写一个递归函数每次调用都负责读取一个完整的“片段”遇到[就递归进去遇到]就返回当前片段。用到的核心是一个全局索引i因为字符串的读取是线性的递归返回后必须接着上次的位置继续读。如果不把索引设为全局或包装成可变对象很容易陷入“每个递归分支都从头开始”的混乱。3.2 递归实现里的几个容易忽略的细节我先给一段Python递归解法def decodeString(s: str) - str: def dfs(): nonlocal i res num 0 while i len(s): ch s[i] if ch.isdigit(): num num * 10 int(ch) i 1 elif ch [: i 1 inner dfs() # 递归解析括号里的内容 res num * inner num 0 elif ch ]: i 1 return res else: res ch i 1 return res i 0 return dfs()这里有三个细节值得反复强调数字可能在递归调用前是0当递归返回后必须把num重置为0否则下一个数字会累加错误。]的处理遇到]要先把i加1跳过这个右括号再返回结果。因为递归返回后外层循环会继续从右括号后面的位置开始读。空字符串的处理如果括号内是空的比如2[]虽然题目没有明说但最好让代码能正常返回空字符串不要越界。有人可能会问递归和栈相比复杂度有差别吗其实没有本质差别时间和空间复杂度都是 O(n)准确说是 O(maxK * n)后面细说。递归写法更贴近“嵌套表达式”的天然结构理解起来更简单但缺点是如果嵌套深度特别大可能引起系统栈溢出。而显式栈没有这个风险这也是为什么力扣官方题解和大多数人都推荐栈解法。我个人建议两种解法都亲手写一遍。先用递归建立直觉再用栈完善工程实现这样面试时无论被问到哪种都能从容应对。4. 复杂度和优化从“能跑”到“跑得好”4.1 时间复杂度到底怎么算maxK与嵌套的关系很多题解会直接写“时间复杂度 O(n)”但这道题的 n 是原始编码串的长度还是解码后字符串的长度这里容易让人混淆。严谨地说假设解码后的最终字符串长度为S那么时间复杂度至少是 O(S)因为你要生成这些字符。而如果编码串里大量使用较大的重复次数比如10000[a]解码结果长度是10000那么算法需要不停拼接耗费 O(S) 的时间。考虑到嵌套比如k1[k2[...]]最终长度可能是指数级增长的所以更准确的上界可以写成O(sum(每个括号内的解码后长度))也就是遍历过程中拼接操作的总次数。举个例子3[a]2[bc]的解码后字符串长度是 2439错了应该是aaabcbc长度7。这都不重要重要的是你要理解如果输入是10[10[a]]输出长度是100你的循环就得拼接100次。所以网上常说的“输出主导型”复杂度就是这个意思。4.2 拼接操作是性能瓶颈如何避免反复创建对象使用String直接相加Java里每次会生成新对象Python里每次也是新字符串这在重复次数大的时候会明显拖慢速度。优化思路有两个使用可变字符序列比如 Java 的StringBuilder或 Python 的list暂存字符最后再join。合并多次重复在栈解法中遇到]时一次性repeat(k)比循环 k 次逐个 append 要好。Java 的StringBuilder没有内置 repeat但可以用cur.repeat(k)配合prev.append或者直接用StringBuilder循环append。实测下来在 k 非常大时循环 k 次 append 本身也是 O(k)所以没有额外问题只是代码没那么优雅。我自己更喜欢在 Java 里用String.repeatJava 11 支持写成cur.repeat(k)再prev.append(...)能少写一个循环可读性也更好。还有一个小技巧如果题目特别强调“不要用任何额外空间”那基本不可能因为栈和递归都需要空间。空间复杂度是 O(嵌套深度 × 当前层的字符串长度)在极端情况下也不小这取决于输入结构而不是算法本身。4.3 测试用例设计比题目给的示例再多想两层边界刷题最忌讳只看题目给的三个示例就提交。我建议至少再测这几类连续多个独立编码块3[a]2[bc]验证前一个块结束后数字和字符串都重置干净。数字后面紧跟数字10[a]验证多位数字解析。括号内以数字开头2[3[a]]验证嵌套时内层的数字也能正确解析。编码块和其他字母混合2[abc]ef验证边界字母正常保留。空串验证直接返回空串。无编码的纯字母abc验证循环正常走完。把这些用例跑一遍代码基本就稳了。我发现很多人恰恰是把a2[c]这类“前有字母后有数字”的组合给写挂所以在测试时一定要加一项编码块前面有普通字母比如ab2[c]确保栈里存的是ab而不是空串。5. 踩坑实录我在写这道题时犯过的错和调试技巧5.1 最隐蔽的bug数字解析不清零导致层层翻倍我第一次用栈解法写这道题时遇到一个很诡异的现象3[a]2[bc]输出aaabcbcbc多了一段。排查半天发现问题出在我遇到[时把curNum入栈了但忘记把curNum清零。于是在第二个编码块解析2时curNum还残留着上一个块的3乘上10再加2变成32。这不是算法思路的问题而是状态管理习惯的问题。后来我给自己定了个规矩每一次“入栈”操作后必须立刻把当前累积变量重置为默认值。这不是这题独有的要求是所有用到“状态栈”的题目的通用原则。5.2 另一个容易翻车的地方字符串拼接的先后顺序再举一个实际例子输入是2[ab3[c]]正确输出是abcabccc不对我重新算一下3[c]ccc所以ab3[c]abccc再重复2次结果是abcccabccc。如果你在弹出栈时把当前展开结果直接覆盖了prev作为前缀比如写成cur cur.repeat(k) prev结果就变成cccabcccab完全错乱。记住这个顺序展开后的内容 弹出来的前缀字符串 当前字符串重复k次。前缀永远在左边当前字符串重复的内容永远在右边。这一点和乘法分配律无关纯粹是编码串的语义决定的k[encoded]中的[encoded]是整体被重复的对象而这个对象前面可能还有别的字符。5.3 调试技巧打印栈状态几分钟就能定位问题如果你也碰到输出不对别盯着代码一行行看直接在遇到[和]时打印当前curStr、curNum、栈的内容。比如print(fchar{c}, cur{cur!r}, num{num}, str_stack{str_stack}, num_stack{num_stack})跑一个3[a2[c]]立刻能看出是入栈时压错了字符串还是出栈时拼接顺序反了。这个方法对栈类题目几乎通杀我靠它解决过不少类似的括号问题。5.4 关于官方题解里“正则替换”的评论为什么不推荐每次这道题下方都有评论说可以用正则(\d)\[([a-z]*)\]循环替换。确实能过示例但遇到嵌套就要反复匹配3[a2[c]]第一次替换只能把2[c]换成cc得到3[acc]再去匹配3[acc]此时正则里的[a-z]*已经包含括号了必须用递归式正则或者加修正。正则不是不行但既慢又难维护面试时更不可能让你去敲一个复杂正则。所以老老实实掌握栈和递归才是正解。6. 从394延伸出去hot100里的同族题目和解题套路6.1 这类“括号重复”题目有什么共同逻辑力扣hot100里和字符串解码同类的题还有不少比如“反转每对括号间的子串”1190、“原子的数量”726、“花括号展开”1087等。它们的共同点是存在括号或嵌套结构内层结果需要先算出来再参与外层计算。这种“由内向外”的依赖关系用栈或递归都能解。我总结了一个通用套路大家可以背下来遇到左分隔符[、(、{把当前上下文入栈并重置遇到右分隔符弹出上下文把内层结果合并进去遇到普通字符直接追加到当前层数字单独解析注意多位数字。这个套路在“计算器”224、227里也适用只是那里的左分隔符是(数字的处理多了一个加减乘除优先级的维度。所以千万别把394当成一道孤立的题目它其实代表了一类“用栈维护上下文”的经典问题。6.2 需要掌握的变体不嵌套但数字在后面的情况有些变体题会把编码规则反过来比如[abc]2表示abc重复两次或者让括号可以嵌套但要求输出展开后的所有可能组合比如花括号展开。处理方式大同小异只需要调整入栈的时机和拼接顺序。还有一道进阶版是“原子的数量”726它需要统计每个原子的个数栈里存的不是字符串而是元素名到数量的映射表。如果你能把394的栈结构彻底想明白再去看726会容易很多——只不过把“字符串拼接”换成了“哈希表合并”。我在刷hot100时就是这样把相关题目放在同一周内解决的效率和记忆持久度都高很多。另外如果面试官要求“不修改原字符串的情况下解码”那就要用递归并通过索引传递当前位置避免重复复制字符串这又回到了递归下降的思路。所以把394的两种解法都吃透相当于掌握了一整类问题的两个兵器。7. 一些个人刷题体会和最后的建议我在刷hot100的过程中发现394这道题特别适合用来检验自己对栈的理解是否到位。原因很简单它不像20. 有效的括号那样只需要配对也不像155. 最小栈那样需要维护附加状态它要求你同时维护两个维度的状态字符串和数字并且在正确的时间点做进栈、出栈、拼接。能把394一次写对说明你对“栈生命周期”有了直觉。关于刷题方法我有一点个人体会不要只抄题解一定要自己动手模拟一个小例子。哪怕是像我上面列的那种表格把一个3[a2[c]]从头到尾画出栈的变化也比看十遍代码有用。因为画完你就知道当前字符串在入栈时代表的是“左括号之前的内容”而不是“左括号之后的内容”——这个容易错的地方画一遍就记住了。最后如果你想验证自己是否真正理解了可以试着把Java解法改写成“只用一个栈”的版本把数字和字符串打包成AbstractMap.SimpleEntry或自定义类。这个练习本身没什么实战价值但它会逼你思考栈顶元素的类型以及如何区分“这是数字”还是“这是字符串”。做完这个练习再回到双栈解法你会觉得一切都是顺理成章的。如果你在刷这道题时卡了很久别灰心。我见过不少工作经验丰富的老程序员第一次写也翻车因为它考的不是会不会写循环而是有没有建立起“用栈保存上下文”的思维模型。一旦建立起来后面的22. 括号生成、32. 最长有效括号这类hard题你也会觉得没那么遥不可及。