DAY 14: LeetCode 394. 字符串解码｜递归和栈到底怎么处理嵌套？

LeetCode 394. 字符串解码｜我是怎么从嵌套想到递归和栈的？

题目链接：394. 字符串解码

弄了个网站, 可以看代码是怎么操作达到最终要的结果: 过程可视化

刚开始看到这道题，我其实没觉得特别难。

例如3[a]，就是把a重复 3 次，得到aaa。

所以我最初的想法很简单：找到数字，确定重复次数，再找到括号里的字符串，把它重复对应的次数。

但遇到3[a2[c]]时，我就卡住了。

因为这里出现了嵌套。

一、真正的问题：为什么必须先处理里面？

以3[a2[c]]为例。

最外层的3[...]不能直接计算，因为括号里面的a2[c]还没有解码完成。

正确的处理顺序应该是：

2[c] → cc a2[c] → acc 3[acc] → accaccacc

也就是说，必须先解决内层，才能得到外层的结果。

如果再多嵌套几层，例如3[a2[b4[c]]]，情况也是一样。

所以真正需要解决的问题是：

程序怎么知道应该先处理哪一层，又怎么在内层处理完以后，回到外层继续计算？

这让我想到了两种办法：递归和栈。

二、方法一：递归

1. 为什么会想到递归？

观察3[a2[c]]：

外层的3[...]要做的是：

先解码括号里的内容，再重复 3 次。

内层的2[c]要做的也是：

先解码括号里的内容，再重复 2 次。

区别只是处理的内容和重复次数不同，但它们解决的其实是同一种问题。

那么, 既然内层和外层的任务一样，能不能让同一个函数再次调用自己，专门去处理内层？

这就是递归的思路。

不过，想到递归只是第一步。接下来还需要确定：一次递归到底负责什么？

2. 一次递归负责处理当前这一层

我决定让每次递归只负责一件事：

从指定位置开始，向右去解析当前层的内容，直到遇到这一层对应的右括号]。

例如：

3 [ a 2 [ c ] ] ↑ 从这里开始处理外层括号的内容

当函数处理到内层的[时，就再调用一次递归，从c开始处理。

因此，函数首先需要知道从哪里开始。

defdfs(i):

这里的i表示当前要读取的字符下标。

当遇到[时，左括号本身不属于需要解码的字符串，所以应该从它后面的字符开始：

sub,i=dfs(i+1)

( 这里 return 出来的东西后面再解释.

至于什么时候停止：

• 普通括号层：遇到属于自己的]就结束。
• 最外层：因为没有对应的]，所以一直处理到字符串末尾。

这样，每次递归负责的范围就明确了。

3. 当前层需要保存哪些信息？

还是以a2[c]为例。

从左往右扫描时，首先遇到a。

这个字符是最终结果的一部分，因此需要保存已经解码出来的字符串：

result=""

遇到字母，就拼接进去：

result+=s[i]

接下来遇到数字2。

它不是结果的一部分，而是告诉我们后面的括号内容需要重复多少次。

因此还需要一个变量：

number=0

所以一次递归主要维护三个信息：

这里有一个很重要的区别：

result是当前层最终要返回的结果，而number只是构造这个结果时使用的临时状态。

4. 遇到不同字符，分别怎么办？

确定了变量以后，就可以按照字符类型设计处理逻辑。

遇到数字 → 更新 number 遇到字母 → 拼接到 result 遇到 [ → 进入下一层递归 遇到 ] → 当前层结束，返回结果

其中最关键的是遇到[的情况。

例如当前层已经处理到：

result = "a" number = 2

这时遇到了[，说明后面的c属于下一层。

当前层先暂停，让下一层去解码。

sub,i=dfs(i+1)

下一层返回：

sub = "c"

然后当前层继续处理：

result+=sub*number

相当于：

"a" + "c" * 2 = "acc"

这里需要弄清楚一点：

重复次数由外层保存，也由外层负责使用。

内层只需要把自己的内容解码出来，不需要知道外层要重复几次。

5. 为什么递归不能只返回字符串？

这里还有一个容易忽略的问题。

假设内层已经返回了"c"。

外层当然知道解码结果是什么，但它还需要知道：

刚才内层处理到了原字符串的哪个位置？接下来应该从哪里继续？

因此，递归不仅需要返回结果，还需要返回停止的位置。

returnresult,i

其中：

• result：当前层解码出来的字符串。
• i：当前层停止时所在的下标；对于普通括号层，就是对应]的位置。

上一层通过：

sub,i=dfs(i+1)

接收这两个值。

由于返回的i指向已经处理完的]，所以外层还需要：

i+=1

跳过这个右括号，继续扫描后面的字符。

因此，i有两个作用：

进入递归时：告诉下一层从哪里开始。 递归返回时：告诉上一层处理到哪里了。

6. 完整走一次：3[a2[c]]2[b]

这个例子比3[a2[c]]多了一个2[b]，正好可以说明：

子递归结束，不代表当前层也结束。

先标出下标：

下标：0 1 2 3 4 5 6 7 8 9 10 11 字符：3 [ a 2 [ c ] ] 2 [ b ]

第一层：

从i = 0开始，读取到数字3：

number = 3 result = ""

接着遇到[，进入第二层。

第二层：

先读取a，再读取2：

result = "a" number = 2

遇到内层[，进入第三层。

第三层：

读取c：

result = "c"

然后遇到下标6的]，返回：

("c",6)

回到第二层：

第二层拿到sub = "c"，结合自己保存的number = 2：

result = "a" + "c" * 2 = "acc"

然后跳过下标6的右括号。

此时马上遇到下标7的另一个]，这才是第二层自己的结束位置。

所以第二层返回：

("acc",7)

回到第一层：

第一层之前保存的number = 3，现在终于可以使用：

result = "" + "acc" * 3 = "accaccacc"

但第一层还没有结束。

因为原字符串后面还有2[b]。

于是继续向右扫描，读取2，再进入新的一层处理b。

最后得到：

"accaccacc" + "b" * 2 = "accaccaccbb"

直到整个字符串扫描结束，第一层才返回最终答案。

7. 完整递归代码

classSolution:defdecodeString(self,s:str)->str:n=len(s)defdfs(i):result=""number=0whilei<n:ifs[i].isdigit():number=number*10+int(s[i])i+=1elifs[i].isalpha():result+=s[i]i+=1elifs[i]=="[":sub,i=dfs(i+1)result+=sub*number number=0i+=1elifs[i]=="]":returnresult,ireturnresult,i answer,_=dfs(0)returnanswer

这里再补充两个细节。

🚩为什么多位数字要写成number * 10 + int(s[i])？

例如123[a]，我们是一个字符一个字符读取的：

读取 1： 0 * 10 + 1 = 1 读取 2： 1 * 10 + 2 = 12 读取 3： 12 * 10 + 3 = 123

每读取一位新数字，就把原来的数字乘以 10，再加上当前数字。

另外，每次完成一个数字[...]结构后，都要把number重置为0。

否则，如果后面还有3[d]，之前的重复次数就可能和新的数字拼在一起。

🚩为什么最后还有一个return result, i？

因为最外层没有对应的]。

它会一直扫描到i == len(s)，然后退出while。

所以需要在循环结束后返回最终结果。

8. 递归的复杂度

设输入字符串长度为n，最终解码结果长度为m，最大括号嵌套深度为d。

• 时间：与输入扫描和字符串构造有关。使用当前的result += ...写法，字符串复制可能产生额外开销，不能简单认为一定是O(n)。
• 空间：递归调用栈需要O(d)，此外还需要存储解码过程中生成的字符串，空间消耗与解码结果及中间字符串有关。

三、方法二：栈

接下来尝试另一种写法。

其实最开始看到嵌套时，我就有过一个想法：

既然外层暂时不能计算，那能不能先把读到的内容存起来，等遇到右括号时，再从后往前处理最近的一层？

前面的递归，是让 Python 的函数调用机制帮我们保存外层状态。

而这一次，我想自己保存这些暂时处理不了的内容，等内层计算完成以后，再继续处理外层。

这就让我想到了栈。

1. 为什么会想到用栈？

还是看3[a2[c]]。

我们已经知道，必须先计算里面的2[c]，才能处理外面的3[...]。

但从左往右扫描时，最先遇到的却是外层：

3 → [ → a → 2 → [ → c → ] → ]

也就是说：

外层先出现 ↓ 内层后出现 ↓ 内层先结束 ↓ 外层最后结束

这恰好符合栈的后进先出。

所以我想：先不急着计算，直接把遇到的字符依次放进栈里。

直到遇到第一个]：

原字符串：3[a2[c]] ↑ 遇到第一个 ]

此时栈中保存着：

["3","[","a","2","[","c"]

第一个]对应的正是最里面的2[c]。

这意味着，最近这一层的内容已经完整了，可以开始解码。

于是问题就变成：

我该怎么从栈里找到这一层的字符串和重复次数？

2. 第一步：怎么找到当前括号里的字符串？

遇到]以后，首先想知道的是：这一层括号里面到底是什么？

例如3[a2[c]]，当前需要取出的就是c。

因为字符都是依次压栈的，所以最近读取的内容就在栈顶。

那就可以从栈顶往回取。

但马上又有一个问题：

如果括号里不止一个字符，而是abc呢？我怎么知道应该取几个？

显然不能只取一次。

而且括号里的内容长度也不固定，不能提前规定取三次、五次。

这时候再细看, 就会发现之前已经把[也压进了栈。

它不正好可以作为边界吗？

所以不需要知道字符串有多长。

只要栈顶还不是[，就说明当前括号里的内容还没有取完。

于是就有了这样的处理思路：

从栈顶取出一个字符串片段 ↓ 保存起来 ↓ 检查栈顶是不是 [ ↓ 不是 → 继续取 是 → 当前括号内容收集完成

因为不知道要重复多少次，所以这里适合使用while。

mid=""whilestack[-1]!="[":current=stack.pop()mid=current+mid

这里的mid用来保存当前括号里的字符串。

不过，为什么是：

mid=current+mid

而不是：

mid+=current

原因也很简单：我们是从右往左取的。

例如括号里面是abc：

先取出 c → mid = "c" 再取出 b → mid = "bc" 最后取 a → mid = "abc"

如果把新取出的字符放在后面，就会错误地得到cba。

另外，栈里也可能存在之前已经解码好的字符串，例如"cc"，所以每次取出的不一定只是单个字符，也可能是一整段字符串。

现在，括号里的内容终于找到了。

但栈顶还留着一个[。

它只是用来标记这一层的边界，既然已经找到边界，就可以把它删除：

stack.pop()

这样，当前括号里的字符串就处理完成了。

3. 第二步：怎么找到重复次数？

字符串已经找到了，接下来还需要知道：

这一层到底要重复多少次？

例如：

12[abc]

前面我们是逐字符压栈的，因此1和2是两个独立的元素。

删除[以后，栈顶就是数字2。

所以可以继续往回取数字。

但这里也有一个问题：

数字可能不止一位，我怎么知道什么时候取完？

其实和刚才寻找括号内容的思路很像。

刚才是遇到[停止。

这次则是：只要栈顶仍然是数字，就继续取。

栈顶是数字 ↓ 取出来 ↓ 继续检查栈顶 ↓ 还是数字 → 继续取 不是数字 → 停止

同样，因为不知道数字有几位，所以也使用while。

num=""whilestackandstack[-1].isdigit():current=stack.pop()num=current+num

为什么这里还多了一个stack存在与否的判定？

因为数字可能位于整个字符串的最前面。

例如12[abc]，当1也被弹出以后，栈就空了。

如果这时还直接访问stack[-1]，就会报错。

因此需要先判断栈是否为空，再检查栈顶是不是数字。

Python 的and具有短路特性，所以：

stackandstack[-1].isdigit()

可以避免访问空栈。

还有一点和刚才一样：数字也是从右往左取出来的。

例如：

先取出 2 → num = "2" 再取出 1 → num = "12"

因此同样要把新取出的字符放在前面：

num=current+num

到这里，我们终于找到了这一层需要的两个信息：

mid → 括号里的字符串 num → 重复次数

4. 第三步：解码后的字符串应该放在哪里？

现在假设我们正在处理3[a2[c]]的内层。

已经得到：

mid = "c" num = "2"

那么：

mid*int(num)

就可以得到：

"cc"

但是，问题又来了。

这个"cc"应该放在哪里？

它显然不能直接作为最终答案。

因为外面还有一层3[...]，而且"cc"前面还有一个a。

如果直接把"cc"放到最终结果里，外层就无法继续使用它了。

所以我想到：

既然它仍然属于外层尚未处理完的内容，那就把它重新放回栈里，不就可以了吗？

于是：

stack.append(mid*int(num))

原来的栈：

["3","[","a","2","[","c"]

处理完内层以后：

["3","[","a","cc"]

相当于把：

3[a2[c]]

逐渐化简成：

3[acc]

注意，这里的acc只是为了方便理解而写出来的。实际上栈里仍然保存着两个片段："a"和"cc"。

接下来继续扫描原字符串。

很快又遇到了第二个]。

这一次不需要想新的处理办法，直接重复刚才的步骤：

从栈顶往回取字符串 ↓ 先取出 "cc"，再取出 "a" ↓ 得到 mid = "acc" ↓ 删除 [ ↓ 继续往回取数字 ↓ 得到 num = "3" ↓ 计算 "acc" * 3 ↓ 得到 "accaccacc"

再把结果压回栈。

每遇到一个]，就把最近的一层解码掉，再把结果放回栈中。

这样即使有很多层嵌套，也不需要提前知道有多少层。

只要重复相同的处理过程，嵌套就会一层一层被消除。

5. 那原字符串的指针需要往回移动吗？

还有一个地方，我当时想得比较绕。

当我们遇到]时，已经知道要从栈顶往回取内容。

但我最初有点困惑：

原字符串的指针i已经走到]了。现在要往回找内容，是不是还需要一个j，专门从右往左移动？

后来才发现，根本不需要。

因为我们不是在原字符串里往回找，而是在已经保存的栈里取内容。

这其实是两件不同的事情：

i：负责从左往右读取原字符串。 stack.pop()：负责从栈顶取出之前保存的内容。

例如：

原字符串：3[a2[c]] ↑ 第一个 ]

当i走到这个]时，暂时不用移动。

接下来只需要通过pop()，完成当前层的解码。

等这一层处理完成，结果也重新压回栈以后，再让i向右移动：

i+=1

因此，整个过程中：

• i始终负责向右扫描原字符串。
• pop()负责从栈里往回取内容。

不需要额外创建一个反向指针。

6. 到这里，完整思路就出来了

回顾一下，我们刚才实际上是一步步解决了这些问题：

外层暂时不能计算 ↓ 先把字符压入栈 ↓ 遇到 ]，说明最近一层已经完整 ↓ 需要找到括号里的字符串 ↓ 不知道长度？ → 一直 pop，直到栈顶是 [ ↓ 删除 [ ↓ 需要找到重复次数 ↓ 不知道有几位？ → 一直 pop，直到栈顶不是数字 ↓ 得到 mid 和 num ↓ 计算 mid * int(num) ↓ 结果仍然属于外层？ → 重新压回栈 ↓ 继续扫描原字符串

有了这个过程，再写代码就比较自然了。

7. 完整栈代码

classSolution:defdecodeString(self,s:str)->str:stack=[]i=0whilei<len(s):ifs[i]!="]":stack.append(s[i])i+=1else:mid=""whilestack[-1]!="[":current=stack.pop()mid=current+mid stack.pop()num=""whilestackandstack[-1].isdigit():current=stack.pop()num=current+num stack.append(mid*int(num))i+=1return"".join(stack)

8. 为什么最后是"".join(stack)？

代码写完以后，我还遇到过一个小问题。

最开始我想直接返回：

returnstack[0]

但答案错误，因为栈里最后不一定只有一个元素。

例如：

2[a]3[b]

先处理2[a]，得到"aa"，然后压回栈：

stack=["aa"]

接着继续扫描，遇到3[b]。

按照前面的逻辑，只要当前字符不是]，就先压入栈。

所以在处理第二个右括号之前，栈会变成：

stack=["aa","3","[","b"]

等3[b]解码完成，再把"bbb"压回栈：

stack=["aa","bbb"]

**所以, 这里是两个元素，而不是直接变成["aabbb"]**

换句话说, 我们之前设计的规则是：

每遇到一个]，就只处理最近的一层括号，再把解码结果作为一个新的元素压回栈。

所以"aa"和"bbb"虽然都已经解码完成，但仍然是栈中的两个独立元素。

这时候如果直接：

returnstack[0]

返回的就只有"aa"，后面的"bbb"被遗漏了。

那怎么办？

既然最后栈里剩下的都是已经解码好的字符串片段，我们只需要把它们按顺序拼接起来。

于是改成：

return"".join(stack)

这里的join()会使用空字符串""作为分隔符，将栈中的所有字符串连接起来：

"".join(["aa","bbb"])# "aabbb"

这样，无论最后栈里是一个元素，还是多个独立的字符串片段，都能得到完整的解码结果。

9. 复杂度分析

设输入字符串长度为n，最终解码结果长度为m。

• 时间：需要扫描输入字符串，并不断进行弹栈、字符串拼接和重复操作。由于 Python 字符串不可变，拼接可能产生额外复制开销，因此当前实现不能简单认为是O(n)，实际耗时还取决于解码过程中生成的字符串长度。
• 空间：栈保存尚未处理的字符和已经解码的字符串片段，空间消耗取决于这些内容的总大小。

四、最后复盘：递归和栈到底有什么联系？

递归这条路：

发现嵌套 ↓ 外层必须等待内层 ↓ 发现内外层其实是同一种任务 ↓ 想到让函数调用自己 ↓ 确定一次递归负责当前层 ↓ 用 i 记录解析位置 ↓ 用 result 保存当前层结果 ↓ 用 number 保存重复次数 ↓ 遇到 [ → 进入下一层 ↓ 遇到 ] → 返回结果和结束位置 ↓ 上一层恢复执行

栈这条路：

发现嵌套 ↓ 外层暂时不能计算 ↓ 先把内容保存起来 ↓ 遇到 ] → 最近的一层完整了 ↓ 从栈顶往回取内容 ↓ 找到字符串和重复次数 ↓ 完成这一层解码 ↓ 把结果重新压回栈 ↓ 继续处理外层

两种方法看起来不一样，但本质上都在解决同一个问题：

当外层还没处理完，却必须先解决内层时，如何保存外层的状态，并在内层完成以后继续处理？

递归利用函数调用栈保存状态；显式栈则由我们自己管理暂时未处理的内容。

遇到嵌套结构时，不一定要急着一次性处理完整个字符串。可以先确定每一层负责什么、什么时候结束，以及处理完以后如何回到上一层。