LeetCode 394. Decode String 题解题目描述给定一个经过编码的字符串返回它解码后的字符串。编码规则为:k[encoded_string]表示其中方括号内部的encoded_string正好重复k次。注意k保证为正整数。你可以认为输入字符串总是有效的输入字符串中没有额外的空格且输入的方括号总是符合格式要求的。此外你可以认为原始数据不包含数字所有的数字只表示重复的次数k例如不会出现像3a或2[4]的输入。示例 1输入s 3[a]2[bc] 输出aaabcbc示例 2输入s 3[a2[c]] 输出accaccacc示例 3输入s 2[abc]3[cd]ef 输出abcabccdcdcdef示例 4输入s abc3[cd]xyz 输出abccdcdcdxyz解题思路方法栈思路使用两个栈一个用于存储数字一个用于存储字符串遍历字符串对于每个字符如果是数字解析出完整的数字并将其压入数字栈如果是左括号将当前字符串压入字符串栈并重置当前字符串如果是右括号弹出数字栈的数字弹出字符串栈的字符串将当前字符串重复数字次然后与弹出的字符串拼接如果是字母将其添加到当前字符串遍历结束后返回当前字符串复杂度分析时间复杂度O(n)其中 n 是解码后字符串的长度。每个字符最多被处理一次。空间复杂度O(n)需要使用栈来存储数字和字符串。代码实现方法栈class Solution: def decodeString(self, s: str) - str: # 初始化数字栈和字符串栈 num_stack [] str_stack [] # 初始化当前字符串和当前数字 current_str current_num 0 # 遍历字符串 for char in s: # 如果是数字 if char.isdigit(): # 解析完整的数字 current_num current_num * 10 int(char) # 如果是左括号 elif char [: # 将当前数字压入数字栈 num_stack.append(current_num) # 将当前字符串压入字符串栈 str_stack.append(current_str) # 重置当前字符串和当前数字 current_str current_num 0 # 如果是右括号 elif char ]: # 弹出数字栈的数字 num num_stack.pop() # 弹出字符串栈的字符串 prev_str str_stack.pop() # 将当前字符串重复数字次然后与弹出的字符串拼接 current_str prev_str current_str * num # 如果是字母 else: # 将其添加到当前字符串 current_str char # 遍历结束后返回当前字符串 return current_str测试用例测试用例 1输入s 3[a]2[bc]输出aaabcbc测试用例 2输入s 3[a2[c]]输出accaccacc测试用例 3输入s 2[abc]3[cd]ef输出abcabccdcdcdef测试用例 4输入s abc3[cd]xyz输出abccdcdcdxyz总结本题是栈的经典应用问题主要考察对栈数据结构的理解和使用。通过使用栈我们可以高效地解码字符串。栈的核心思想是使用两个栈一个用于存储数字一个用于存储字符串当遇到左括号时将当前数字和字符串压入栈中当遇到右括号时弹出数字和字符串将当前字符串重复数字次然后与弹出的字符串拼接。这种方法不仅适用于字符串解码问题还可以应用于许多其他需要处理嵌套结构的问题。掌握栈的使用对于解决这类问题非常重要。