🚀 力扣热题 394：字符串解码（详细解析）
📌 题目描述
力扣 394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为：
k[encoded_string]，表示其中方括号内部的encoded_string正好重复k次。你可以认为k总是一个正数。注意：输入字符串中只包含数字、英文字母、方括号
[]和不会嵌套的数字。
🌟 示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"
🌟 示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"
🌟 示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
💡 解题思路
✅ 栈结构（Stack）解法
这是一个经典的 栈应用题，核心思路是：
- 遇到
[：将当前数字（重复次数）和字符串入栈。 - 遇到
]：弹出栈顶元素，构造新字符串。 - 遇到字母：追加到当前字符串中。
我们维护两个栈：
- 数字栈：存储重复次数。
- 字符串栈：存储括号外的字符串。
💻 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 == ']' {
repeat := numStack[len(numStack)-1]
numStack = numStack[:len(numStack)-1]
prevStr := strStack[len(strStack)-1]
strStack = strStack[:len(strStack)-1]
temp := ""
for i := 0; i < repeat; i++ {
temp += currStr
}
currStr = prevStr + temp
} else {
currStr += string(ch)
}
}
return currStr
}
✅ 方法二：递归解法
另一种常见的解法是使用递归。递归的思想是将当前字符串按照解码规则拆解，每次遇到 ] 就进行一层解码，然后返回结果。我们通过递归调用来处理字符串中的每一部分。
递归思路：
- 遇到数字时，开始收集数字，表示重复次数。
- 遇到 [ 时，递归解析其中的字符串，并将解码后的部分乘以数字。
- 遇到 ] 时，返回当前的结果并将结果拼接到之前的解码字符串中。
步骤：
- 遇到字母，直接拼接到当前的解码字符串。
- 遇到数字，记录并构建重复次数。
- 遇到 [ 时，开始递归调用处理括号内的字符串。
- 遇到 ] 时，返回当前解析的结果并继续处理外部字符串。
✅ 方法二：递归解法
```go
func decodeString(s string) string {
index := 0
return decodeHelper(s, &index)
}
func decodeHelper(s string, index int) string {
res := ""
for index < len(s) {
ch := s[index]
if ch >= '0' && ch <= '9' {
num := 0
for index < len(s) && s[index] >= '0' && s[index] <= '9' {
num = num10 + int(s[index]-'0')
index++
} index++ // skip '['
str := decodeHelper(s, index)
index++ // skip ']'
for i := 0; i < num; i++ {
res += str
}
} else if ch == ']' {
return res
} else {
res += string(ch) index++
}
}
return res
}
```
【比较分析】
| 方法 | 特点 | 处理步骤 | 处理嵌套性 | 应用场景 |
|---|---|---|---|---|
| 栈解法 | 简洁直观，便于理解 | 递渐构造字符串 | 支持嵌套 | 适合初学者 |
| 递归解法 | 逻辑清晰，方便处理嵌套结构 | 循环解析，函数循环构造结果 | 更适合深度嵌套规则 | 高级结构处理 |
⏳ 复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 栈/递归 | $O(n)$ | $O(n)$ |
n是字符串长度，遍历一遍，各步操作均为常数时间- 空间用于栈或递归调用的结果缓存
🌟 总结
- 栈和递归都是解决本题的有效途径
- 栈解法更加简单直观，适合初学和面试习题
- 递归解法适合处理庞复的嵌套规则，优雅简洁
💡 成熟掌握两种思路，能使你展现多样化的解题技巧。
