文章目录摘要描述题解答案题解代码分析为什么用两个栈数字怎么解析遇到 [ 时在做什么遇到 ] 时在做什么遇到字母时示例 2 简要过程3[a2[c]]示例测试及结果示例 1s 3[a]2[bc]示例 2s 3[a2[c]]示例 3s 2[abc]3[cd]ef示例 4s abc3[cd]xyz边界单层无嵌套时间复杂度空间复杂度实际应用场景总结摘要这道题要求把一种编码后的字符串解码回来。编码规则是k[encoded_string]方括号里的串重复 k 次且允许嵌套例如3[a2[c]]表示先得到acc再整体重复 3 次得到accaccacc。做法是顺序扫描字符串用两个栈分别保存「当前层之前的已解码结果」和「当前层要重复的次数」遇到数字就解析出 k 并入栈遇到[就把当前已解码串入栈并清空当前串遇到]就弹栈得到 k 和上一层串把当前串重复 k 次拼到上一层后面作为新的当前串遇到字母就直接拼到当前串。最后当前串即为整体解码结果。下面用 Swift 实现并说明细节。描述给定一个经过编码的字符串返回它解码后的字符串。编码规则为k[encoded_string]表示方括号内部的encoded_string正好重复 k 次。k 保证为正整数。输入保证有效没有多余空格方括号成对出现。原始数据不包含数字所有数字只表示重复次数 k例如不会出现3a或2[4]。测试用例保证解码后长度不超过 10^5。示例 1输入 s 3[a]2[bc] 输出 aaabcbc示例 2输入 s 3[a2[c]] 输出 accaccacc示例 3输入 s 2[abc]3[cd]ef 输出 abcabccdcdcdef示例 4输入 s abc3[cd]xyz 输出 abccdcdcdxyz提示1 s.length 30s由小写英文字母、数字和方括号[]组成s保证有效所有整数在[1, 300]范围内核心思路用栈模拟「进入一层括号」和「退出一层括号」。进入时记住「当前已解码串」和「这一层的 k」退出时把当前层串重复 k 次拼回上一层这样自然支持任意层嵌套。题解答案classSolution{funcdecodeString(_s:String)-String{varresultvarcountStack:[Int][]varstringStack:[String][]letarrArray(s)vari0whileiarr.count{letcarr[i]ifc.isNumber{varnum0whileiarr.countarr[i].isNumber{numnum*10Int(String(arr[i]))!i1}countStack.append(num)}elseifc[{stringStack.append(result)resulti1}elseifc]{letkcountStack.removeLast()letprevstringStack.removeLast()resultprevString(repeating:result,count:k)i1}else{result.append(c)i1}}returnresult}}题解代码分析为什么用两个栈一层方括号对应「一个重复次数 k」和「进入这层括号之前已经得到的解码串」。遇到]时需要知道「这一层要重复几次」countStack 栈顶和「上一层已经拼到哪里了」stringStack 栈顶。所以用两个栈分别存数字和字符串遇到]时各弹一个把当前层串重复 k 次后拼到上一层后面再作为新的「当前串」继续往后扫。数字怎么解析题目里 k 可能是多位数例如 12、100。所以遇到数字时不能只读一位要用循环while i arr.count arr[i].isNumber把连续数字都读完用num num * 10 Int(String(arr[i]))!拼成整数再入 countStack。循环结束后i停在[上下一轮会处理[。遇到[时在做什么[表示进入新的一层编码。此时当前result是「这一层括号之前」已经解码好的前缀可能是空串也可能是前面一段字母或上一层解码结果。把result压入 stringStack再把result清空表示从现在开始积累的是「这一层括号内的内容」。对应的 k 已经在上一轮读数字时压入 countStack 了。遇到]时在做什么]表示当前层结束。从 countStack 弹出 k从 stringStack 弹出上一层的串 prev。当前result就是这一层括号内的解码串重复 k 次得到String(repeating: result, count: k)再拼到 prev 后面result prev String(repeating: result, count: k)。这样 result 又变成「到本层为止」的完整解码串可以继续往后处理或作为最终结果。遇到字母时既不在括号内参与「重复」的嵌套结构也不是数字或括号直接result.append(c)作为当前已解码串的一部分。示例 2 简要过程3[a2[c]]读到3num3countStack[3]i 到[。读到[stringStack[“”]result“”i 到a。读到aresult“a”。读到2num2countStack[3,2]i 到[。读到[stringStack[“”,“a”]result“”。读到cresult“c”。读到]k2prev“a”result“a”“cc”“acc”。读到]k3prev“”result“”“accaccacc”“accaccacc”。返回 “accaccacc”。示例测试及结果示例 1s “3[a]2[bc]”解码为 “aaa” “bcbc” “aaabcbc”与预期一致。示例 2s “3[a2[c]]”内层 2[c] 得 “cc”与 “a” 拼成 “acc”外层 3[acc] 得 “accaccacc”。示例 3s “2[abc]3[cd]ef”2[abc] → “abcabc”3[cd] → “cdcdcd”再拼 “ef”得到 “abcabccdcdcdef”。示例 4s “abc3[cd]xyz”前面 “abc”中间 3[cd] → “cdcdcd”后面 “xyz”得到 “abccdcdcdxyz”。边界单层无嵌套例如 “1[a]” 得到 “a”“10[a]” 得到 “aaaaaaaaaa”。数字解析正确、重复次数正确即可。时间复杂度每个字符最多入栈、出栈或参与一次拼接。整体扫描一遍栈操作和字符串拼接次数与 s 长度和嵌套层数相关解码后串长最多 10^5可视为 O(n 输出长度)。若把每次String(repeating:count:)的代价算上最坏约为 O(输出长度)。空间复杂度countStack 和 stringStack 的深度不超过括号嵌套层数与 s 长度同阶result 和拼接产生的临时串与解码后长度相关。可视为 O(嵌套深度 解码后长度)。实际应用场景类似规则常用于简单压缩或协议一段内容用「重复次数 内容」表示节省长度。解码逻辑和本题一致用栈处理嵌套即可。前端或网关里解析带压缩的配置、模板串时也会用到这类「括号 数字」的解析方式。总结字符串解码的关键是「括号与重复次数」的匹配与嵌套。用两个栈分别保存每一层的重复次数和进入该层前的已解码串遇到数字就解析完整 k 并入栈遇到[就保存当前串并清空遇到]就弹栈并做「上一层 当前串重复 k 次」遇到字母直接拼接。这样一层层处理最后得到的即为完整解码结果。