LeetCode 394:字符串解码——Java 单栈模拟与嵌套解析详解
一、题目描述给定一个经过编码的字符串编码格式为k[encoded_string]它表示方括号中的encoded_string需要重复k次其中k是正整数。例如输入s 3[a]2[bc] 输出aaabcbc表达式3[a]解码为aaa2[bc]解码为bcbc拼接后得到aaabcbc。编码还可能嵌套输入s 3[a2[c]] 输出accaccacc这里必须先把内部的2[c]解码为cc再把外部的a2[c]还原为acc最后重复三次。由此可以发现本题具有明显的“后进入、先处理”特征非常适合使用栈。二、为什么使用栈当我们从左到右扫描字符串时在遇到右括号]之前并不知道当前括号内的内容是否已经完整。因此可以先把数字、字母和左括号依次压入栈中。右括号]表示当前最内层表达式已经结束。此时从栈顶向前弹出元素顺序恰好是括号内字符串 → 左括号 [ → 重复次数将这一组内容解码后再把结果压回栈中。后续如果遇到外层右括号刚刚得到的字符串就会作为外层内容继续参与解码。所以栈能够自然保证最内层括号先被处理外层括号后被处理。三、遍历字符串的处理规则准备一个StackString逐个扫描输入字符串中的字符。1. 当前字符不是右括号数字、字母和左括号都直接压栈stack.push(String.valueOf(ch));例如扫描3[a后栈中内容为[3, [, a]2. 当前字符是右括号遇到]时不需要将它压栈而是立即完成一次局部解码弹出字符并拼接直到栈顶是[弹出左括号继续弹出左括号前连续的数字将括号内字符串重复指定次数把展开后的新字符串重新压栈。四、如何恢复括号内字符串假设栈顶依次是字符c、b它们原来的顺序应该是bc。由于栈是后进先出如果直接把弹出的字符追加到末尾就会错误地得到cb。因此必须把每次弹出的字符放到temp前面String temp ; while (!stack.peek().equals([)) { temp stack.pop() temp; }执行过程为弹出 ctemp c 弹出 btemp b c bc当栈顶变成[时说明当前括号内的内容已经全部取出随后弹出左括号stack.pop();五、如何解析多位重复次数重复次数不一定只有一位例如12[a]字符1和2是分别入栈的。弹栈时会先得到2再得到1因此同样需要从前面拼接String num ; while (!stack.isEmpty() Character.isDigit(stack.peek().charAt(0))) { num stack.pop() num; }这样才能得到字符串12而不是21。随后将其转换为整数int repeatNum Integer.parseInt(num);题目保证输入合法并且k是正整数所以标准输入中num不会为空也不会出现重复零次的情况。六、展开后为什么还要压回栈得到temp和repeatNum后将temp重复指定次数StringBuilder newStr new StringBuilder(); for (int i 0; i repeatNum; i) { newStr.append(temp); }然后把结果压回栈中stack.push(newStr.toString());这样既能处理多个并列表达式也能处理嵌套表达式。例如3[a2[c]]遇到内部第一个]将2[c]解码为cc并压栈此时外层内容在逻辑上变成3[acc]遇到外层]再把acc重复三次。这就是栈从内到外解析嵌套结构的过程。七、完整 Java 代码下面的代码严格使用截图中的单栈思路import java.util.Stack; class Solution { public String decodeString(String s) { StackString stack new Stack(); for (char ch : s.toCharArray()) { if (ch ! ]) { // 数字、字母和左括号直接入栈 stack.push(String.valueOf(ch)); continue; } // 1. 取出当前最内层括号中的字符串 String temp ; while (!stack.peek().equals([)) { temp stack.pop() temp; } // 2. 弹出左括号 stack.pop(); // 3. 解析左括号前的多位重复次数 String num ; while (!stack.isEmpty() Character.isDigit(stack.peek().charAt(0))) { num stack.pop() num; } int repeatNum Integer.parseInt(num); // 4. 将字符串重复指定次数 StringBuilder newStr new StringBuilder(); for (int i 0; i repeatNum; i) { newStr.append(temp); } // 5. 将局部解码结果重新压栈 stack.push(newStr.toString()); } // 栈中可能存在多个并列片段需要按原顺序拼接 String result ; while (!stack.isEmpty()) { result stack.pop() result; } return result; } }八、示例完整推演以s 3[a]2[bc]为例。1. 处理3[a]扫描到第一个右括号前栈为[3, [, a]遇到]弹出a得到temp a弹出[弹出数字3得到repeatNum 3将a重复三次得到aaa把aaa压入栈中。此时stack [aaa]2. 处理2[bc]继续扫描2[bc后stack [aaa, 2, [, b, c]遇到第二个]先弹出c再弹出b得到temp bc弹出[和数字2将bc重复两次得到bcbc把bcbc压栈。最终栈为[aaa, bcbc]遍历结束后按照原顺序拼接栈中片段得到aaa bcbc aaabcbc九、复杂度分析设最终解码字符串长度为N。每个输入字符会被压栈、弹栈展开字符串本身还需要实际生成因此时间复杂度可表示为O(N)。这里的N应按解码后的结果规模计算而不能只看原字符串长度。栈和中间字符串最多需要保存解码结果中的字符空间复杂度为O(N)。需要注意代码中使用stack.pop() temp和最终的字符串头部拼接Java 字符串不可变极端情况下会产生额外复制开销。但本文严格遵循截图的单栈拼接方案若追求更高性能可以进一步使用StringBuilder优化拼接。十、常见错误1. 把右括号也压入栈右括号是触发解码的信号遇到后应立即处理当前最内层结构。2. 弹出的字符直接追加到末尾栈的弹出顺序与原字符串相反应使用temp stack.pop() temp;否则bc会被拼成cb。3. 只弹出一个数字重复次数可能是多位数必须连续弹出所有相邻数字并注意恢复原顺序。4. 解码结果没有重新入栈如果不将局部结果压回栈外层表达式就无法继续使用内层解码结果嵌套结构会解析失败。5. 最后直接顺序弹栈拼接最终弹栈顺序仍然与原顺序相反因此需要将弹出的片段放到结果字符串前面。十一、总结字符串解码的核心是利用栈处理括号嵌套的“后进先出”关系。遍历过程中除右括号外的字符全部入栈每遇到一个]就依次弹出括号内字符串、左括号和重复次数完成一次最内层解码再把结果压回栈中。

相关新闻

Kickflip Android SDK与AWS S3集成:实现直播内容的安全存储与分发

Kickflip Android SDK与AWS S3集成:实现直播内容的安全存储与分发

Kickflip Android SDK与AWS S3集成:实现直播内容的安全存储与分发 【免费下载链接】kickflip-android-sdk Kickflip Android SDK - Live Video Streaming to the Cloud 项目地址: https://gitcode.com/gh_mirrors/ki/kickflip-android-sdk Kickflip Android …

2026/11/18 13:50:31 阅读更多 →
MediaCrawler 免费开源社交媒体数据采集终极指南:五个平台一个框架通吃

MediaCrawler 免费开源社交媒体数据采集终极指南:五个平台一个框架通吃

MediaCrawler 免费开源社交媒体数据采集终极指南:五个平台一个框架通吃 【免费下载链接】MediaCrawler-new 项目地址: https://gitcode.com/GitHub_Trending/me/MediaCrawler-new 凌晨三点,市场部的分析师小林还盯着浏览器,一篇篇复制…

2026/11/18 13:58:30 阅读更多 →
Krokiet 重复文件清理工具终极指南:5 步找回磁盘空间

Krokiet 重复文件清理工具终极指南:5 步找回磁盘空间

Krokiet 重复文件清理工具终极指南:5 步找回磁盘空间 【免费下载链接】czkawka Multi functional app to find duplicates, empty folders, similar images etc. 项目地址: https://gitcode.com/GitHub_Trending/cz/czkawka 你的磁盘是不是又变红了&#xff…

2026/11/18 13:58:30 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/18 13:59:04 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/18 15:33:23 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/18 17:05:28 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/18 14:33:19 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/18 17:05:28 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/18 14:13:08 阅读更多 →

日新闻

周新闻

月新闻