LeetCode 热题 100 394. 字符串解码

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

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

一、问题描述

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

二、解题思路

（一）栈的巧妙应用

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

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

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

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

（三）代码实现

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

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

（四）代码解析

1. 初始化：

   • stack：用于存储解码过程中的中间结果和重复次数。
   • cur_str：用于存储当前的解码结果。
   • cur_num：用于存储当前的重复次数。

2. 遍历字符串：

   • 遍历输入字符串 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
     

3. 返回最终结果：

   • 遍历结束后，cur_str 即为最终的解码结果。

三、复杂度分析

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

四、总结

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

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