394. 字符串解码
394. 字符串解码中等给定一个经过编码的字符串返回它解码后的字符串。编码规则为:k[encoded_string]表示其中方括号内部的encoded_string正好重复k次。注意k保证为正整数。你可以认为输入字符串总是有效的输入字符串中没有额外的空格且输入的方括号总是符合格式要求的。此外你可以认为原始数据不包含数字所有的数字只表示重复的次数k例如不会出现像3a或2[4]的输入。测试用例保证输出的长度不会超过105。示例 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保证是一个有效的输入。s中所有整数的取值范围为[1, 300] 核心笔记字符串解码 (Decode String)1. 核心思想 (一句话总结)“遇到字母直接拿遇到数字找配对拆解成 [重复内容] [后缀]。”我们将字符串看作是一个数学表达式。基本情况如果是字母直接保留处理下一个字符。复杂情况如果是数字说明后面跟着一个k[...]的结构。我们需要找到这个结构匹配的右括号将其拆解为三部分次数k。内容t括号里面的部分需递归解码。后缀右括号后面的剩余部分需递归解码。2. 算法流程 (分治法)Base Case字符串为空 - 返回空。Case A: 头部是字母提取首字母 decode(剩下部分)。Case B: 头部是数字找左括号确定数字的结束位置i解析出倍数k。找匹配的右括号 (关键)从左括号开始向右扫维护一个balance计数器。遇[加一遇]减一。当balance 0时说明找到了匹配的](位置j)。递归组合结果 k个decode(内部)decode(后缀)。 代码回忆清单 (带注释版)// 题目LC 394. Decode String class Solution { public String decodeString(String s) { // 1. Base Case if (s.isEmpty()) { return s; } // 2. 情况一当前是字母不需要重复 if (Character.isLetter(s.charAt(0))) { // 贪心策略其实可以连续读完所有字母再一次性递归减少递归深度 // 但这里逐个字符递归逻辑更简单统一 return s.charAt(0) decodeString(s.substring(1)); } // 3. 情况二当前是数字形如 k[...]suffix int i s.indexOf([); // 数字结束左括号开始的位置 // 4. 寻找匹配的右括号 (核心难点) // 不能直接 s.indexOf(])因为可能有嵌套如 3[a2[c]] int balance 1; // 已经遇到了 s[i] 这个左括号 for (int j i 1; ; j) { // 从左括号后面开始找 char c s.charAt(j); if (c [) { balance; } else if (c ]) { balance--; // 5. 找到匹配的闭环 if (balance 0) { // 解析次数 k int k Integer.parseInt(s.substring(0, i)); // 递归解决括号内部 (t) String t decodeString(s.substring(i 1, j)); // 拼接结果k 个 t 递归解决后缀 // 注意StringBuilder.repeat 是 Java 21 新特性 // 如果是老版本 Java可以用 t.repeat(k) (Java 11) 或手动循环 return new StringBuilder() .repeat(t, k) .append(decodeString(s.substring(j 1))) .toString(); } } } } }⚡ 快速复习 CheckList (易错点)[ ]为什么不能直接找第一个]输入可能是3[a2[c]]。第一个]是c后面的那个。如果直接截取会把3[和2[c]错误地配对。必须使用balance计数器来处理嵌套。[ ]时间复杂度这种递归写法的复杂度较高。因为s.substring在 Java 中是 $O(N)$ 的拷贝数组且每一层递归都可能创建新的子串。虽然逻辑清晰但在字符串非常长且嵌套深的情况下性能不如“双栈法”(StackInteger count, StackString res)。[ ]API 版本注意new StringBuilder().repeat(t, k)是JDK 21的 API。如果是 JDK 11可以用sb.append(t.repeat(k))。如果是 JDK 8需要手动写个for循环 appendk次。️ 脑图模型 (拆信封)输入3[a2[c]]b第一层拆解数字3。信封内容a2[c](待解码)。后缀b(待解码)。任务3 * decode(a2[c]) decode(b)第二层拆解 (a2[c])首字符a- 拿出a剩下2[c]。任务a decode(2[c])第三层拆解 (2[c])数字2。信封内容c。后缀 (空)。任务2 * c -cc回溯组装L2 返回a ccaccL1 返回3 * acc baccaccaccb
)
