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）来处理，因为嵌套的结构（例如 3[a2[c]] ）需要从内层括号开始解码，这与栈的后进先出（LIFO）特性相符。 我们遍历字符串，遇到非 ] 的字符就压入栈，遇到 ] 时开始出栈，直到遇到 [ ，这之间的字符就是需要重复的子串；然后继续出栈得到重复的数字（注意数字可能有多位），将子串重复指定次数后，再重新压入栈（因为外层可能还有嵌套）。最后栈中剩下的就是解码后的结果。 详细步骤 初始化栈 创建一个栈（比如用列表模拟），用于存储字符和中间结果。 遍历字符串的每个字符 如果当前字符不是 ] ，直接压入栈。 如果当前字符是 ] ，开始解码过程： a. 从栈中弹出字符，直到遇到 [ ，这些字符组成一个子串（注意顺序是反的，需要反转）。 b. 弹出 [ 。 c. 继续弹出字符，直到栈为空或栈顶不是数字，这些字符是重复次数 k（数字可能有多位，需要从后往前拼接）。 d. 将子串重复 k 次，得到新的字符串。 e. 将新字符串的每个字符重新压入栈（因为可能还有外层嵌套）。 最终结果 遍历结束后，栈中字符从底到顶连接起来就是解码后的字符串。 举例说明 以 s = "3[ a2[ c] ]" 为例： 遍历到 ] 前，栈是 ['3', '[', 'a', '2', '[', 'c'] 。 遇到第一个 ] ： 弹出直到 [ ，得到子串 "c" ，k = 2，新串 "cc" 压回栈： ['3', '[', 'a', 'c', 'c'] 。 继续遍历到 ] ： 弹出直到 [ ，子串 "acc" ，k = 3，新串 "accaccacc" 压回栈。 栈中最终结果 "accaccacc" 。 复杂度分析 时间复杂度：O(n)，n 是输出字符串的长度。 空间复杂度：O(n)，栈的最大深度可能达到 n。 通过栈处理嵌套结构，每一步确保内层括号先被解码，逻辑清晰且高效。