LeetCode 第 394 题：字符串解码（Decode String）

字数 2823 2025-10-27 16:36:47

LeetCode 第 394 题：字符串解码（Decode String）

题目描述

给定一个经过编码的字符串，要求将它解码返回原始字符串。

编码规则为：k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

解题过程

这个问题需要处理嵌套的括号和重复次数，我们可以使用栈（Stack）来辅助处理，因为栈的“后进先出”特性很适合处理嵌套结构。

步骤 1：理解核心难点

嵌套结构：比如 3[a2[c]]，我们需要先解码内层的 2[c] 得到 "cc"，然后再与外层结合，变成 a + cc = "acc"，最后重复 3 次。
多位数：重复次数 k 可能不是一位数，比如 10[a] 或 100[leetcode]，所以我们需要解析出完整的数字。

步骤 2：设计算法思路
我们可以遍历字符串的每一个字符，并分别处理以下四种情况：

数字：遇到数字，说明开始了一个新的重复模式。我们需要解析出完整的数字（因为可能有多位）。
左括号 [：左括号标志着重复内容 encoded_string 的开始。此时，我们需要将当前已经解析好的数字和当前已经构建好的字符串分别压入栈中暂存起来。然后重置数字和当前字符串，为处理内层嵌套做准备。
- 压入数字栈：记录当前这个重复模式需要重复的次数。
- 压入字符串栈：记录在遇到这个内层嵌套之前，已经解码好的字符串部分。
右括号 ]：右括号标志着当前这个重复模式的结束。此时，我们需要进行“出栈”和“展开”操作：
- 从数字栈弹出栈顶数字（记为 current_k），它表示当前这个内层字符串需要重复的次数。
- 从字符串栈弹出栈顶字符串（记为 last_string），它是在当前内层嵌套之前已经解码好的部分。
- 将当前正在构建的字符串（即内层解码的结果）重复 current_k 次。
- 将重复后的字符串拼接到 last_string 的后面，这个结果成为新的“当前字符串”。
普通字母：如果遇到的是英文字母，只需要将它追加到“当前正在构建的字符串”的末尾即可。

步骤 3：详细步骤演示（以 s = "3[a2[c]]" 为例）

我们初始化两个栈：num_stack (存放数字k) 和 str_stack (存放字符串)。同时初始化 current_num = 0 和 current_str = ""。

遍历字符串 3[a2[c]]：

字符 ‘3’：是数字。current_num = 3。
字符 ‘[’：是左括号。
- 将 current_num (3) 压入 num_stack。栈状态: num_stack: [3]
- 将 current_str ("") 压入 str_stack。栈状态: str_stack: [""]
- 重置 current_num = 0, current_str = ""。
字符 ‘a’：是字母。追加到 current_str。current_str = "a"。
字符 ‘2’：是数字。current_num = 2。
字符 ‘[’：是左括号。
- 将 current_num (2) 压入 num_stack。栈状态: num_stack: [3, 2]
- 将 current_str ("a") 压入 str_stack。栈状态: str_stack: ["", "a"]
- 重置 current_num = 0, current_str = ""。
字符 ‘c’：是字母。追加到 current_str。current_str = "c"。
字符 ‘]’：是右括号。开始关键的解码操作：
- 从 num_stack 弹出栈顶数字：current_k = 2。栈状态: num_stack: [3]
- 从 str_stack 弹出栈顶字符串：last_str = "a"。栈状态: str_stack: [""]
- 将 current_str ("c") 重复 current_k (2) 次，得到 "cc"。
- 将 last_str ("a") 和 "cc" 拼接，成为新的 current_str。current_str = "a" + "cc" = "acc"。
- （注意：此时内层的 2[c] 已经解码完成并融入外层字符串中）
字符 ‘]’：是右括号。再次进行解码操作：
- 从 num_stack 弹出栈顶数字：current_k = 3。栈状态: num_stack: []
- 从 str_stack 弹出栈顶字符串：last_str = ""。栈状态: str_stack: []
- 将 current_str ("acc") 重复 current_k (3) 次，得到 "accaccacc"。
- 将 last_str ("") 和 "accaccacc" 拼接，成为新的 current_str。current_str = "" + "accaccacc" = "accaccacc"。

遍历结束，最终结果就是 current_str，即 "accaccacc"。

步骤 4：代码实现要点

使用一个循环遍历字符串 s。
使用 Character.isDigit(c) 来判断字符是否是数字。
遇到数字时，需要用 current_num = current_num * 10 + (c - '0') 来累加多位数。
遇到左括号 [，进行入栈和重置操作。
遇到右括号 ]，进行出栈、字符串展开和拼接操作。
遇到字母，直接添加到 current_str。

这个算法的时间复杂度是 O(n)，其中 n 是输出字符串的长度（因为每个字符可能被处理多次，但展开操作的总和与输出长度线性相关）。空间复杂度在最坏嵌套情况下为 O(n)，用于栈的存储。

LeetCode 第 394 题：字符串解码（Decode String）题目描述给定一个经过编码的字符串，要求将它解码返回原始字符串。编码规则为： k[encoded_string] ，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。示例 1：输入：s = "3[ a]2[ bc ]" 输出："aaabcbc" 示例 2：输入：s = "3[ a2[ c] ]" 输出："accaccacc" 示例 3：输入：s = "2[ abc]3[ cd ]ef" 输出："abcabccdcdcdef" 解题过程这个问题需要处理嵌套的括号和重复次数，我们可以使用栈（Stack）来辅助处理，因为栈的“后进先出”特性很适合处理嵌套结构。步骤 1：理解核心难点嵌套结构：比如 3[a2[c]] ，我们需要先解码内层的 2[c] 得到 "cc" ，然后再与外层结合，变成 a + cc = "acc" ，最后重复 3 次。多位数：重复次数 k 可能不是一位数，比如 10[a] 或 100[leetcode] ，所以我们需要解析出完整的数字。步骤 2：设计算法思路我们可以遍历字符串的每一个字符，并分别处理以下四种情况：数字：遇到数字，说明开始了一个新的重复模式。我们需要解析出完整的数字（因为可能有多位）。左括号 [ ：左括号标志着重复内容 encoded_string 的开始。此时，我们需要将当前已经解析好的数字和当前已经构建好的字符串分别压入栈中暂存起来。然后重置数字和当前字符串，为处理内层嵌套做准备。压入数字栈：记录当前这个重复模式需要重复的次数。压入字符串栈：记录在遇到这个内层嵌套之前，已经解码好的字符串部分。右括号 ] ：右括号标志着当前这个重复模式的结束。此时，我们需要进行“出栈”和“展开”操作：从数字栈弹出栈顶数字（记为 current_k ），它表示当前这个内层字符串需要重复的次数。从字符串栈弹出栈顶字符串（记为 last_string ），它是在当前内层嵌套之前已经解码好的部分。将当前正在构建的字符串（即内层解码的结果）重复 current_k 次。将重复后的字符串拼接到 last_string 的后面，这个结果成为新的“当前字符串”。普通字母：如果遇到的是英文字母，只需要将它追加到“当前正在构建的字符串”的末尾即可。步骤 3：详细步骤演示（以 s = "3[ a2[ c]]" 为例）我们初始化两个栈： num_stack (存放数字k) 和 str_stack (存放字符串)。同时初始化 current_num = 0 和 current_str = "" 。遍历字符串 3[a2[c]] ：字符 ‘3’ ：是数字。 current_num = 3 。字符 ‘[’ ：是左括号。将 current_num (3) 压入 num_stack 。栈状态: num_ stack: [ 3 ] 将 current_str ("") 压入 str_stack 。栈状态: str_ stack: [ "" ] 重置 current_num = 0 , current_str = "" 。字符 ‘a’ ：是字母。追加到 current_str 。 current_str = "a" 。字符 ‘2’ ：是数字。 current_num = 2 。字符 ‘[’ ：是左括号。将 current_num (2) 压入 num_stack 。栈状态: num_ stack: [ 3, 2 ] 将 current_str ("a") 压入 str_stack 。栈状态: str_ stack: [ "", "a" ] 重置 current_num = 0 , current_str = "" 。字符 ‘c’ ：是字母。追加到 current_str 。 current_str = "c" 。字符 ‘]’ ：是右括号。开始关键的解码操作：从 num_stack 弹出栈顶数字： current_k = 2 。栈状态: num_ stack: [ 3 ] 从 str_stack 弹出栈顶字符串： last_str = "a" 。栈状态: str_ stack: [ "" ] 将 current_str ("c") 重复 current_k (2) 次，得到 "cc" 。将 last_str ("a") 和 "cc" 拼接，成为新的 current_str 。 current_str = "a" + "cc" = "acc" 。（注意：此时内层的 2[c] 已经解码完成并融入外层字符串中）字符 ‘]’ ：是右括号。再次进行解码操作：从 num_stack 弹出栈顶数字： current_k = 3 。栈状态: num_ stack: [ ] 从 str_stack 弹出栈顶字符串： last_str = "" 。栈状态: str_ stack: [ ] 将 current_str ("acc") 重复 current_k (3) 次，得到 "accaccacc" 。将 last_str ("") 和 "accaccacc" 拼接，成为新的 current_str 。 current_str = "" + "accaccacc" = "accaccacc" 。遍历结束，最终结果就是 current_str ，即 "accaccacc" 。步骤 4：代码实现要点使用一个循环遍历字符串 s 。使用 Character.isDigit(c) 来判断字符是否是数字。遇到数字时，需要用 current_num = current_num * 10 + (c - '0') 来累加多位数。遇到左括号 [ ，进行入栈和重置操作。遇到右括号 ] ，进行出栈、字符串展开和拼接操作。遇到字母，直接添加到 current_str 。这个算法的时间复杂度是 O(n)，其中 n 是输出字符串的长度（因为每个字符可能被处理多次，但展开操作的总和与输出长度线性相关）。空间复杂度在最坏嵌套情况下为 O(n)，用于栈的存储。