我来给你讲解 LeetCode 第 394 题“字符串解码”。

题目描述

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为：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]] → a 外面是 3 次，c 外面是 2 次。
• 需要把内层括号展开的结果拼接到外层。

逐步推导

第 1 步：分析例子

以 3[a2[c]] 为例：

• 看到 3[，说明接下来要重复 3 次括号里的内容。
• 括号里的内容是 a2[c]：
  • 先有字符 a，
  • 然后遇到 2[，重复 2 次 c，得到 acc。
• 所以内层结果是 acc，再重复 3 次：accaccacc。

第 2 步：确定栈里存什么

因为嵌套时，外层需要记住：

1. 当前已经积累的字符串（在遇到数字和左括号之前的部分）。
2. 当前数字（重复次数）。

所以可以用两个栈：

• countStack：存放当前层的重复次数。
• stringStack：存放当前层在左括号之前的字符串。

第 3 步：遍历规则

初始化：

• currentString = ""
• currentNum = 0

遍历每个字符 c：

1. 如果 c 是数字（'0'~'9'）：
   • 更新 currentNum = currentNum * 10 + (c - '0')
2. 如果 c 是 '['：
   • 把 currentString 压入 stringStack（这是括号前的字符串）
   • 把 currentNum 压入 countStack
   • 重置 currentString = ""，currentNum = 0（准备记录括号内的内容）
3. 如果 c 是 ']'：
   • 从 countStack 弹出重复次数 count
   • 从 stringStack 弹出之前保存的字符串 prevString
   • 更新 currentString = prevString + currentString重复count次
4. 如果 c 是字母：
   • 直接添加到 currentString

第 4 步：示例推演

以 3[a2[c]] 为例：

初始：currentString = "", currentNum = 0

1. 读到 '3'：currentNum = 3
2. 读到 '['：
   • stringStack 压入 ""
   • countStack 压入 3
   • currentString = "", currentNum = 0
3. 读到 'a'：currentString = "a"
4. 读到 '2'：currentNum = 2
5. 读到 '['：
   • stringStack 压入 "a"
   • countStack 压入 2
   • currentString = "", currentNum = 0
6. 读到 'c'：currentString = "c"
7. 读到 ']'：
   • 弹出 count = 2，弹出 prevString = "a"
   • currentString = "a" + "c"*2 = "acc"
8. 读到 ']'：
   • 弹出 count = 3，弹出 prevString = ""
   • currentString = "" + "acc"*3 = "accaccacc"

结果正确。

代码实现（Python）

def decodeString(s: str) -> str:
    stack = []
    current_string = ""
    current_num = 0
    
    for c in s:
        if c.isdigit():
            current_num = current_num * 10 + int(c)
        elif c == '[':
            # 遇到左括号，把当前字符串和数字压栈
            stack.append(current_string)
            stack.append(current_num)
            current_string = ""
            current_num = 0
        elif c == ']':
            # 遇到右括号，弹出数字和前字符串
            num = stack.pop()
            prev_string = stack.pop()
            current_string = prev_string + current_string * num
        else:
            # 字母直接追加
            current_string += c
    
    return current_string

复杂度分析

• 时间复杂度：O(n)，n 为字符串长度，每个字符处理一次。
• 空间复杂度：O(n)，栈的最大深度与嵌套深度有关。

总结

这个题的关键是理解用栈保存每一层的状态（数字和之前的字符串），遇到右括号时弹出并拼接。通过模拟这个过程，可以处理任意深度的嵌套编码。