LeetCode 热题 100 394. 字符串解码-EW帮帮网

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 = 0
        for 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 = '', 0
            elif string == ']':
                last_str, last_num = stack.pop(-1)
                cur_str = last_str + cur_str * last_num
            else:  # 字母
                cur_str = cur_str + string
        return 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 即为最终的解码结果。

三、复杂度分析

时间复杂度：O(n)，其中 n 是输入字符串的长度。每个字符最多被处理两次（一次入栈，一次出栈）。
空间复杂度：O(n)，栈的深度最多为嵌套的层数，每层存储的字符串长度最多为 n。

四、总结

通过使用栈，我们可以高效地处理嵌套的解码问题。栈用于存储当前的解码结果和重复次数，通过逐字符解析输入字符串，我们可以逐步构建出最终的解码结果。这种方法不仅简单易懂，而且时间复杂度和空间复杂度都很低。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！

LeetCode 热题 100 394. 字符串解码