1. 问题背景与需求分析
字符串解码是算法面试中的经典题型，在LeetCode题库中被标记为中等难度（题号394）。这道题出现在Hot100榜单中，说明它是高频考点，考察求职者对栈结构的灵活应用能力。
题目要求我们实现一个解码规则：当遇到形如k[encoded_string]的模式时，需要将encoded_string重复k次。这种嵌套结构可能有多层，例如3[a2[c]]应该被解码为accaccacc。
2. 核心解题思路解析
2.1 栈结构的适用性分析
这类嵌套结构解析问题，栈是最自然的选择：
- 遇到
[时压栈当前状态 - 遇到
]时弹栈处理 - 需要同时保存重复次数和已解码字符串
def decodeString(s: str) -> str: stack = [] current_str = "" current_num = 02.2 字符处理的四种情况
遍历字符串时需要区分四种情况：
- 数字字符：累积计算重复次数
- 字母字符：拼接到当前字符串
[符号：保存当前状态到栈]符号：弹栈并处理嵌套结构
特别注意数字可能有多位（如"100[leetcode]"），需要用isdigit()判断并累积计算
3. 完整算法实现与注释
3.1 Python版本实现
def decodeString(s: str) -> str: stack = [] current_str = "" current_num = 0 for char in s: if char.isdigit(): current_num = current_num * 10 + int(char) elif char == '[': stack.append((current_str, current_num)) current_str = "" current_num = 0 elif char == ']': prev_str, num = stack.pop() current_str = prev_str + num * current_str else: current_str += char return current_str3.2 关键步骤说明
- 数字处理：遇到连续数字时，通过
current_num = current_num * 10 + int(char)实现多位数的解析 - 压栈时机：遇到
[时将当前字符串和数字作为元组压栈，然后重置状态 - 弹栈处理：遇到
]时取出栈顶的字符串和数字，进行字符串拼接
4. 复杂度分析与优化
4.1 时间复杂度
- 最坏情况：O(n×k)，其中n是字符串长度，k是最大重复次数
- 示例：对于
10[a10[b10[c]]]，需要处理10×10×10次拼接
4.2 空间复杂度
- 栈的最大深度取决于嵌套层数
- 最坏情况：O(n)（当所有字符都是
[或]时）
5. 常见错误与调试技巧
5.1 典型错误案例
数字累积错误：
# 错误写法 current_num = int(char) # 只能处理单位数栈操作顺序错误：
# 错误写法 stack.append((current_num, current_str)) # 顺序反了会导致类型错误
5.2 调试建议
使用简单测试用例验证：
"3[a]2[bc]"→"aaabcbc""2[abc]3[cd]ef"→"abcabccdcdcdef"
打印栈状态辅助调试：
print(f"Push: {current_str}, {current_num}")
6. 变种问题与扩展思考
6.1 支持转义字符
如果输入字符串包含转义字符（如\），需要额外处理：
elif char == '\\': i += 1 current_str += s[i]6.2 递归解法实现
虽然栈解法更直观，但也可以使用递归：
def decodeString(s, i=0): res = "" while i < len(s) and s[i] != ']': if not s[i].isdigit(): res += s[i] i += 1 else: num = 0 while i < len(s) and s[i].isdigit(): num = num * 10 + int(s[i]) i += 1 i += 1 # skip '[' decoded, i = decodeString(s, i) i += 1 # skip ']' res += num * decoded return res, i在实际面试中，建议优先展示栈解法，因为递归解法可能因为嵌套过深导致栈溢出，且空间复杂度不易优化。
