LeetCode 热题 100 394. 字符串解码

LeetCode 热题 100 | 394. 字符串解码

大家好！今天我们来探讨一道非常有趣的算法题目——LeetCode 394. 字符串解码。这道题考察了我们对栈这种数据结构的理解和应用能力，同时也涉及到了字符串的处理技巧。接下来，我将详细地为大家解析这道题的解题思路和代码实现。

一、问题描述

题目要求我们给定一个经过编码的字符串，返回它解码后的字符串。编码规则为：k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。输入字符串总是有效的，且不会包含额外的空格。

二、解题思路

（一）栈的巧妙应用

这道题的关键在于利用栈来处理嵌套的解码问题。栈在这里起到了存储中间解码结果和重复次数的作用。通过栈，我们可以方便地处理多层嵌套的情况，确保在解码过程中不会出现混乱。

（二）遍历字符串，逐步解码

我们需要从左到右遍历整个输入字符串，根据遇到的不同字符类型，采取不同的处理策略：

遇到数字：我们需要将数字字符转换为整数，并将其存储起来，因为这表示接下来的字符串需要重复的次数。
遇到 [：这表示一个新的解码单元的开始。我们将当前的解码结果和重复次数作为一个元组压入栈中，然后重置当前的解码结果和重复次数，以便开始处理新的解码单元。
遇到 ]：这表示当前解码单元的结束。我们需要从栈中弹出最近的解码结果和重复次数，将当前的解码结果重复指定的次数，并将其拼接到弹出的解码结果后面。
遇到字母：直接将字母添加到当前的解码结果中。

（三）代码实现

接下来，我将给出详细的代码实现，并对代码中的关键部分进行解释。

class Solution(object):def decodeString(self, s):""":type s: str:rtype: str"""stack = []cur_str = ''cur_num = 0for string in s:if string.isdigit():cur_num = cur_num * 10 + int(string)elif string == '[':stack.append((cur_str, cur_num))cur_str, cur_num = '', 0elif string == ']':last_str, last_num = stack.pop(-1)cur_str = last_str + cur_str * last_numelse:  # 字母cur_str = cur_str + stringreturn cur_str

（四）代码解析

初始化：
- stack：用于存储解码过程中的中间结果和重复次数。
- cur_str：用于存储当前的解码结果。
- cur_num：用于存储当前的重复次数。
遍历字符串：
- 遍历输入字符串 s，逐字符处理每个字符 string。
处理数字：
- 如果 string 是数字，更新 cur_num：
```
cur_num = cur_num * 10 + int(string)
```
  这一步是为了处理多位数的情况。例如，对于字符串 "123"，逐步解析为 1、12、123。
处理 [：
- 如果 string 是 [，将当前的解码结果和重复次数压入栈，并重置 cur_str 和 cur_num：
```
stack.append((cur_str, cur_num))
cur_str, cur_num = '', 0
```
处理 ]：
- 如果 string 是 ]，从栈中弹出最近的解码结果和重复次数，将当前解码结果重复指定次数，并拼接到弹出的解码结果后面：
```
last_str, last_num = stack.pop(-1)
cur_str = last_str + cur_str * last_num
```
处理字母：
- 如果 string 是字母，直接将其添加到 cur_str：
```
cur_str = cur_str + string
```
返回最终结果：
- 遍历结束后，cur_str 即为最终的解码结果。