LeetCode 第 394 题：字符串解码（Decode String） 题目描述 给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为： k[encoded_string] ，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。 示例： 输入：s = "3[ a]2[ bc ]" 输出："aaabcbc" 输入：s = "3[ a2[ c] ]" 输出："accaccacc" 输入：s = "2[ abc]3[ cd ]ef" 输出："abcabccdcdcdef" 解题过程 这个问题可以用栈来处理，因为存在嵌套的编码规则（例如 3[a2[c]] ），需要从内层括号开始解码，符合栈的后进先出特性。 步骤 1：理解核心模式 遇到数字：需要解析出完整的数字（因为可能有多位数，如"123"）。 遇到字母：直接添加到当前结果中。 遇到 [ ：表示开始一个子串，需要将当前状态（当前结果、当前数字）入栈，然后重置临时变量。 遇到 ] ：表示一个子串结束，需要将栈顶元素出栈，并将当前子串重复相应次数后，附加到上层结果中。 步骤 2：详细步骤说明 初始化一个栈（用于存储临时状态）、当前数字 num = 0 、当前字符串 res = "" 。 遍历字符串 s 的每个字符 c： 如果 c 是数字（'0' <= c <= '9'）： 更新当前数字： num = num * 10 + int(c) （处理多位数）。 如果 c 是字母： 将 c 添加到当前结果 res 中。 如果 c 是 ' [ '： 将当前状态（ res 和 num ）入栈：先压入 res ，再压入 num 。 然后重置 res = "" 和 num = 0 （开始记录子串的内容）。 如果 c 是 ' ]'： 说明一个子串结束，需要处理重复： 弹出栈顶元素（是数字，表示重复次数 repeat_count ）。 再弹出栈顶元素（是之前的结果字符串 prev_res ）。 将当前 res 重复 repeat_count 次，然后附加到 prev_res 后面，形成新的当前结果 res = prev_res + res * repeat_count 。 遍历结束后，返回 res 。 步骤 3：示例演示（s = "3[ a2[ c]]"） 初始： num=0, res="", stack=[] 遍历： '3'：数字， num=3 ' [ '：将当前状态入栈： stack = ["", 3] ，然后重置 num=0, res="" 'a'：字母， res="a" '2'：数字， num=2 ' [ '：入栈： stack = ["", 3, "a", 2] ，重置 num=0, res="" 'c'：字母， res="c" ']'：弹出栈顶 repeat_count=2 ，再弹出 prev_res="a" ，更新 res = "a" + "c"*2 = "acc" ']'：弹出栈顶 repeat_count=3 ，再弹出 prev_res="" ，更新 res = "" + "acc"*3 = "accaccacc" 返回 "accaccacc" 步骤 4：代码实现要点 使用栈存储字符串和数字。 注意数字可能是多位数，需要累加计算。 遇到 [ 时，当前状态入栈后要重置；遇到 ] 时，弹出状态并合并结果。 这个解法时间复杂度 O(n)，空间复杂度 O(n)，能高效处理嵌套编码字符串。