编码规则#

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

假设和约束#

• 输入字符串总是有效的。
• 输入字符串中没有额外的空格。
• 输入的方括号总是符合格式要求的（即括号是平衡的）。
• 原始数据不包含数字，所有的数字只表示重复的次数 k。例如，不会出现像 3a 或 2[4] 这样的输入。
• 解码后的字符串最大长度保证不超过 10^5。

示例#

提示#

• 1 <= s.length <= 30
• s 由小写英文字母、数字（0-9）和方括号 '[' 和 ']' 组成
• s 保证是一个有效的输入
• s 中所有整数的取值范围为 [1, 300]

核心思想#

这是一个典型的栈应用问题。由于编码字符串可能包含嵌套结构（如示例 2 中的 3[a2[c]]），我们需要使用栈来保存外层的信息，以便在处理完内层后能够正确恢复。

算法步骤#

1. 使用栈存储上下文：栈中存储 (重复次数, 前缀字符串) 的元组，用于保存遇到 [ 之前的状态。

2. 遍历字符串，根据不同字符类型进行处理：

   • 数字字符：连续读取所有数字字符，转换为整数，作为后续 [...] 的重复次数。
   • 左方括号 [：遇到 [ 时，说明即将开始一个新的编码块。此时将当前的重复次数和已构建的字符串压入栈中保存，然后重置当前状态（重复次数设为 0，字符串清空），准备处理内层内容。
   • 右方括号 ]：遇到 ] 时，说明当前编码块结束。从栈中弹出之前保存的状态 (pre_num, pre_str)，将当前字符串重复 pre_num 次，然后拼接到 pre_str 后面，作为新的当前字符串。
   • 英文字母：直接添加到当前字符串中。

3. 返回结果：遍历完成后，当前字符串即为解码后的结果。

算法示例#

以 "3[a2[c]]" 为例，演示算法执行过程：

• 遇到 3：cur_num = 3
• 遇到 [：将 (3, "") 压入栈，重置 cur_num = 0, cur_str = []
• 遇到 a：cur_str = ['a']
• 遇到 2：cur_num = 2
• 遇到 [：将 (2, "a") 压入栈，重置 cur_num = 0, cur_str = []
• 遇到 c：cur_str = ['c']
• 遇到 ]：弹出 (2, "a")，cur_str = ["a" + 2 * "c"] = ["acc"]
• 遇到 ]：弹出 (3, "")，cur_str = ["" + 3 * "acc"] = ["accaccacc"]
• 返回 "accaccacc"

时间复杂度#

• 时间复杂度：$O(n)$，其中 n 是解码后字符串的长度。每个字符最多被处理一次。
• 空间复杂度：$O(n)$，栈的空间复杂度取决于嵌套层数，最坏情况下为 $O(n)$。