🚀 LeetCode 热题 394：字符串解码（多种方法详解）
📌 题目描述
394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为：
k[encoded_string]，表示其中方括号内部的encoded_string正好重复k次。你可以认为k总是一个正整数。输入字符串中可能存在嵌套的
k[encoded_string]表达式。示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
💡 解题思路
这个题本质是对嵌套结构的解析，有两种经典的解法：
- ✅ 解法一：使用两个栈 —— 适合迭代模拟解析过程，结构清晰。
- ✅ 解法二：使用递归 DFS —— 利用函数递归处理嵌套，结构简洁，代码优雅。
✅ 解法一：栈模拟解码过程
🔧 思路：
- 初始化两个栈：
- 数字栈：记录每次遇到
[前的重复次数k - 字符串栈：记录每层解码前的字符串
- 数字栈：记录每次遇到
- 遍历字符串：
- 遇到数字：累积多位数字
- 遇到
[：将当前数字和字符串压栈，重置 - 遇到
]：弹出数字和字符串，拼接重复结果 - 遇到字符：追加到当前字符串
💻 Go 实现：
func decodeString(s string) string {
numStack := []int{
}
strStack := []string{
}
currStr := ""
num := 0
for _, ch := range s {
if ch >= '0' && ch <= '9' {
num = num*10 + int(ch - '0')
} else if ch == '[' {
numStack = append(numStack, num)
strStack = append(strStack, currStr)
num = 0
currStr = ""
} else if ch == ']' {
times := numStack[len(numStack)-1]
numStack = numStack[:len(numStack)-1]
prev := strStack[len(strStack)-1]
strStack = strStack[:len(strStack)-1]
temp := ""
for i := 0; i < times; i++ {
temp += currStr
}
currStr = prev + temp
} else {
currStr += string(ch)
}
}
return currStr
}
✅ 解法二：递归解法（DFS）
🔧 思路：
利用递归函数模拟解码过程：
- 从当前位置
i开始解析 - 遇到数字解析出
k - 进入递归，解析括号内的字符串
- 遇到
]返回当前解码结果和位置 - 字符串拼接返回
💻 Go 实现：
func decodeString(s string) string {
i := 0
return dfs(s, &i)
}
func dfs(s string, i *int) string {
res := ""
num := 0
for *i < len(s) {
ch := s[*i]
if ch >= '0' && ch <= '9' {
num = num*10 + int(ch - '0')
} else if ch == '[' {
*i++
str := dfs(s, i)
for j := 0; j < num; j++ {
res += str
}
num = 0
} else if ch == ']' {
return res
} else {
res += string(ch)
}
*i++
}
return res
}
⏳ 复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 栈解法 | O(n) | O(n) |
| 递归解法 | O(n) | O(n)（递归栈空间） |
n为字符串长度。- 每个字符都只被处理一次。
📌 解法对比
| 解法 | 优点 | 缺点 |
|---|---|---|
| 栈模拟 | 清晰直观，容易调试 | 手动管理栈，代码略繁琐 |
| 递归 DFS | 简洁优雅，天然处理嵌套 | 递归深度过大可能栈溢出 |
🧠 注意事项
- 多位数字解析：
10[a]应正确解析为重复 10 次 - 字母和数字交错出现的处理
- 嵌套括号的递归调用与括号匹配问题
- 指针或索引的控制要精确
🎯 总结
- 本题属于 字符串嵌套解析类题目，是表达式求值、括号匹配等题型的典型代表。
- 掌握两种解法可以应对不同场景：
- 简单题推荐使用 栈
- 更复杂嵌套结构使用 递归 更简洁
- 需要特别注意 多位数字解析 和 括号控制逻辑
如果你觉得这篇文章对你有帮助，欢迎点赞 👍、收藏 ⭐、关注 🧠！
我会持续更新高质量 LeetCode 热题解析，与你一起刷题成长！💪💻🔥
🎯 标签推荐：字符串解析 递归 栈结构 中等题 面试高频
