LeetCode 第 394 题：字符串解码 题目描述 给定一个经过编码的字符串，返回它解码后的字符串。编码规则为 k[encoded_string] ，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；没有额外空格，且输入的方括号总是符合格式要求。此外，你可以认为原始数据不包含数字，所有数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。 示例： 输入：s = "3[ a]2[ bc ]" 输出："aaabcbc" 输入：s = "3[ a2[ c] ]" 输出："accaccacc" 解题过程 1. 问题分析 该题核心是处理嵌套的括号结构，例如 3[a2[c]] 需要先解内层 2[c] 得到 cc ，再解外层 3[acc] 。这种嵌套结构适合用栈（Stack）或递归（DFS）处理，因为需要先处理内层括号，再处理外层，符合后进先出（LIFO）的特性。 2. 栈解法思路 使用两个栈： countStack ：存储重复次数 k 。 stringStack ：存储当前层之前的字符串片段。 遍历字符串时，分四种情况处理： 遇到数字 ：解析连续的数字字符，组合成整数 k （注意数字可能有多位，如 "123"）。 遇到左括号 [ ：将当前 k 压入 countStack ，当前字符串压入 stringStack ，并重置 k 和当前字符串。 遇到右括号 ] ：从栈中弹出次数 k 和之前字符串，将当前字符串重复 k 次后，拼接到之前字符串的末尾。 遇到字母 ：直接添加到当前字符串末尾。 3. 逐步演示示例 "3[ a2[ c]]" 初始化：当前字符串 res = "" ，当前数字 k = 0 ，栈为空。 遍历字符： 字符 '3' ：数字，更新 k = 3 。 字符 '[' ：将 k=3 压入 countStack ， res="" 压入 stringStack ，重置 k=0 ， res="" 。 字符 'a' ：字母， res = "a" 。 字符 '2' ：数字，更新 k=2 。 字符 '[' ：将 k=2 压入 countStack ， res="a" 压入 stringStack ，重置 k=0 ， res="" 。 字符 'c' ：字母， res = "c" 。 字符 ']' ： 弹出 countStack 栈顶 k=2 ，弹出 stringStack 栈顶 prevStr="a" 。 将 res="c" 重复 2 次得到 "cc" ，拼接到 prevStr 后： res = "a" + "cc" = "acc" 。 字符 ']' ： 弹出 countStack 栈顶 k=3 ，弹出 stringStack 栈顶 prevStr="" 。 将 res="acc" 重复 3 次得到 "accaccacc" ，拼接到 prevStr 后： res = "" + "accaccacc" = "accaccacc" 。 最终结果： "accaccacc" 。 4. 代码实现要点 数字可能连续出现，需用 k = k * 10 + (ch - '0') 累加。 遇到左括号时，当前状态（数字和字符串）入栈，表示开始处理新一层括号。 遇到右括号时，栈顶元素出栈，将当前字符串重复指定次数后拼接，继续处理外层。 5. 复杂度分析 时间复杂度：O(n)，n 为输入字符串长度，每个字符处理一次。 空间复杂度：O(n)，栈深度最多为括号层数，最坏情况下需要线性空间。 总结 本题通过栈模拟递归过程，逐步解析嵌套结构。关键是在左括号时保存状态，右括号时恢复状态并拼接字符串。掌握栈的入栈和出栈时机，即可高效解决问题。