当前位置：首页 > news >正文

394. 字符串解码

news 2026/3/26 17:34:03

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 <= 30
s由小写英文字母、数字和方括号'[]'组成
s保证是一个有效的输入。
s中所有整数的取值范围为[1, 300]

📝 核心笔记：字符串解码 (Decode String)

1. 核心思想 (一句话总结)

“遇到字母直接拿，遇到数字找配对，拆解成 [重复内容] + [后缀]。”

我们将字符串看作是一个数学表达式。

基本情况：如果是字母，直接保留，处理下一个字符。
复杂情况：如果是数字，说明后面跟着一个k[...]的结构。我们需要找到这个结构匹配的右括号，将其拆解为三部分：

1. 次数k。
2. 内容t：括号里面的部分（需递归解码）。
3. 后缀：右括号后面的剩余部分（需递归解码）。

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)$ 的（拷贝数组），且每一层递归都可能创建新的子串。
- 虽然逻辑清晰，但在字符串非常长且嵌套深的情况下，性能不如“双栈法”(Stack<Integer> count, Stack<String> res)。