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,idfs(i1)( 这里 return 出来的东西后面再解释.至于什么时候停止普通括号层遇到属于自己的]就结束。最外层因为没有对应的]所以一直处理到字符串末尾。这样每次递归负责的范围就明确了。3. 当前层需要保存哪些信息还是以a2[c]为例。从左往右扫描时首先遇到a。这个字符是最终结果的一部分因此需要保存已经解码出来的字符串result遇到字母就拼接进去results[i]接下来遇到数字2。它不是结果的一部分而是告诉我们后面的括号内容需要重复多少次。因此还需要一个变量number0所以一次递归主要维护三个信息变量作用i当前读取到哪个位置result当前层已经解码出来的字符串number接下来括号内容需要重复的次数这里有一个很重要的区别result是当前层最终要返回的结果而number只是构造这个结果时使用的临时状态。4. 遇到不同字符分别怎么办确定了变量以后就可以按照字符类型设计处理逻辑。遇到数字 → 更新 number 遇到字母 → 拼接到 result 遇到 [ → 进入下一层递归 遇到 ] → 当前层结束返回结果其中最关键的是遇到[的情况。例如当前层已经处理到result a number 2这时遇到了[说明后面的c属于下一层。当前层先暂停让下一层去解码。sub,idfs(i1)下一层返回sub c然后当前层继续处理resultsub*number相当于a c * 2 acc这里需要弄清楚一点重复次数由外层保存也由外层负责使用。内层只需要把自己的内容解码出来不需要知道外层要重复几次。5. 为什么递归不能只返回字符串这里还有一个容易忽略的问题。假设内层已经返回了c。外层当然知道解码结果是什么但它还需要知道刚才内层处理到了原字符串的哪个位置接下来应该从哪里继续因此递归不仅需要返回结果还需要返回停止的位置。returnresult,i其中result当前层解码出来的字符串。i当前层停止时所在的下标对于普通括号层就是对应]的位置。上一层通过sub,idfs(i1)接收这两个值。由于返回的i指向已经处理完的]所以外层还需要i1跳过这个右括号继续扫描后面的字符。因此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开始读取到数字3number 3 result 接着遇到[进入第二层。第二层先读取a再读取2result a number 2遇到内层[进入第三层。第三层读取cresult c然后遇到下标6的]返回(c,6)回到第二层第二层拿到sub c结合自己保存的number 2result 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:nlen(s)defdfs(i):resultnumber0whilein:ifs[i].isdigit():numbernumber*10int(s[i])i1elifs[i].isalpha():results[i]i1elifs[i][:sub,idfs(i1)resultsub*number number0i1elifs[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。midwhilestack[-1]![:currentstack.pop()midcurrentmid这里的mid用来保存当前括号里的字符串。不过为什么是midcurrentmid而不是midcurrent原因也很简单我们是从右往左取的。例如括号里面是abc先取出 c → mid c 再取出 b → mid bc 最后取 a → mid abc如果把新取出的字符放在后面就会错误地得到cba。另外栈里也可能存在之前已经解码好的字符串例如cc所以每次取出的不一定只是单个字符也可能是一整段字符串。现在括号里的内容终于找到了。但栈顶还留着一个[。它只是用来标记这一层的边界既然已经找到边界就可以把它删除stack.pop()这样当前括号里的字符串就处理完成了。3. 第二步怎么找到重复次数字符串已经找到了接下来还需要知道这一层到底要重复多少次例如12[abc]前面我们是逐字符压栈的因此1和2是两个独立的元素。删除[以后栈顶就是数字2。所以可以继续往回取数字。但这里也有一个问题数字可能不止一位我怎么知道什么时候取完其实和刚才寻找括号内容的思路很像。刚才是遇到[停止。这次则是只要栈顶仍然是数字就继续取。栈顶是数字 ↓ 取出来 ↓ 继续检查栈顶 ↓ 还是数字 → 继续取 不是数字 → 停止同样因为不知道数字有几位所以也使用while。numwhilestackandstack[-1].isdigit():currentstack.pop()numcurrentnum为什么这里还多了一个stack存在与否的判定因为数字可能位于整个字符串的最前面。例如12[abc]当1也被弹出以后栈就空了。如果这时还直接访问stack[-1]就会报错。因此需要先判断栈是否为空再检查栈顶是不是数字。Python 的and具有短路特性所以stackandstack[-1].isdigit()可以避免访问空栈。还有一点和刚才一样数字也是从右往左取出来的。例如先取出 2 → num 2 再取出 1 → num 12因此同样要把新取出的字符放在前面numcurrentnum到这里我们终于找到了这一层需要的两个信息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向右移动i1因此整个过程中i始终负责向右扫描原字符串。pop()负责从栈里往回取内容。不需要额外创建一个反向指针。6. 到这里完整思路就出来了回顾一下我们刚才实际上是一步步解决了这些问题外层暂时不能计算 ↓ 先把字符压入栈 ↓ 遇到 ]说明最近一层已经完整 ↓ 需要找到括号里的字符串 ↓ 不知道长度 → 一直 pop直到栈顶是 [ ↓ 删除 [ ↓ 需要找到重复次数 ↓ 不知道有几位 → 一直 pop直到栈顶不是数字 ↓ 得到 mid 和 num ↓ 计算 mid * int(num) ↓ 结果仍然属于外层 → 重新压回栈 ↓ 继续扫描原字符串有了这个过程再写代码就比较自然了。7. 完整栈代码classSolution:defdecodeString(self,s:str)-str:stack[]i0whileilen(s):ifs[i]!]:stack.append(s[i])i1else:midwhilestack[-1]![:currentstack.pop()midcurrentmid stack.pop()numwhilestackandstack[-1].isdigit():currentstack.pop()numcurrentnum stack.append(mid*int(num))i1return.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 保存重复次数 ↓ 遇到 [ → 进入下一层 ↓ 遇到 ] → 返回结果和结束位置 ↓ 上一层恢复执行栈这条路发现嵌套 ↓ 外层暂时不能计算 ↓ 先把内容保存起来 ↓ 遇到 ] → 最近的一层完整了 ↓ 从栈顶往回取内容 ↓ 找到字符串和重复次数 ↓ 完成这一层解码 ↓ 把结果重新压回栈 ↓ 继续处理外层两种方法看起来不一样但本质上都在解决同一个问题当外层还没处理完却必须先解决内层时如何保存外层的状态并在内层完成以后继续处理递归利用函数调用栈保存状态显式栈则由我们自己管理暂时未处理的内容。遇到嵌套结构时不一定要急着一次性处理完整个字符串。可以先确定每一层负责什么、什么时候结束以及处理完以后如何回到上一层。