LeetCode 热题 100 394. 字符串解码

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

各人好！今天我们来探讨一道非常风趣的算法标题——LeetCode 394. 字符串解码。这道题观察了我们对栈这种数据布局的理解和应用能力，同时也涉及到了字符串的处理惩罚技巧。接下来，我将详细地为各人剖析这道题的解题思路和代码实现。
一、问题形貌

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

（一）栈的奇妙应用

这道题的关键在于利用栈来处理惩罚嵌套的解码问题。栈在这里起到了存储中心解码结果和重复次数的作用。通过栈，我们可以方便地处理惩罚多层嵌套的环境，确保在解码过程中不会出现杂乱。
（二）遍历字符串，逐步解码

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

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

（三）代码实现

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

1. class Solution(object):
2.     def decodeString(self, s):
3.         """
4.         :type s: str
5.         :rtype: str
6.         """
7.         stack = []
8.         cur_str = ''
9.         cur_num = 0
10.         for string in s:
11.             if string.isdigit():
12.                 cur_num = cur_num * 10 + int(string)
14.             elif string == '[':
15.                 stack.append((cur_str, cur_num))
16.                 cur_str, cur_num = '', 0
17.             elif string == ']':
18.                 last_str, last_num = stack.pop(-1)
19.                 cur_str = last_str + cur_str * last_num
20.             else:  # 字母
21.                 cur_str = cur_str + string
23.         return cur_str

复制代码

（四）代码剖析

• 初始化：
  
  
  
  • stack：用于存储解码过程中的中心结果和重复次数。
    
  • cur_str：用于存储当前的解码结果。
    
  • cur_num：用于存储当前的重复次数。
    
  
  
• 遍历字符串：
  
  
  
  • 遍历输入字符串 s，逐字符处理惩罚每个字符 string。
    
  处理惩罚数字：
     
  
  
  
  • 如果 string 是数字，更新 cur_num：
    1. cur_num = cur_num * 10 + int(string)

    复制代码
    这一步是为了处理惩罚多位数的环境。例如，对于字符串 "123"，逐步剖析为 1、12、123。
    
  处理惩罚 [：
     
  
  
  
  • 如果 string 是 [，将当前的解码结果和重复次数压入栈，并重置 cur_str 和 cur_num：
    1. stack.append((cur_str, cur_num))
    2. cur_str, cur_num = '', 0

    复制代码
  处理惩罚 ]：
     
  
  
  
  • 如果 string 是 ]，从栈中弹出最近的解码结果和重复次数，将当前解码结果重复指定次数，并拼接到弹出的解码结果背面：
    1. last_str, last_num = stack.pop(-1)
    2. cur_str = last_str + cur_str * last_num

    复制代码
  处理惩罚字母：
     
  
  
  
  • 如果 string 是字母，直接将其添加到 cur_str：
    1. cur_str = cur_str + string

    复制代码
  
  
• 返回最终结果：
  
  
  
  • 遍历竣事后，cur_str 即为最终的解码结果。
    
  
  

三、复杂度分析

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

四、总结

通过利用栈，我们可以高效地处理惩罚嵌套的解码问题。栈用于存储当前的解码结果和重复次数，通过逐字符剖析输入字符串，我们可以逐步构建出最终的解码结果。这种方法不仅简单易懂，而且时间复杂度和空间复杂度都很低。希望这篇题解对各人有所资助，如果有任何问题，欢迎在评论区留言讨论！
关注我，获取更多算法题解和编程技巧！