题解 | #牛牛的字符串解码问题# Python3
牛牛的字符串解码问题
https://www.nowcoder.com/practice/e5658311e6d44b74872e843ba13ee290
要解码给定的字符串,我们可以使用栈来辅助处理。遍历字符串 s 中的每个字符,根据不同的情况进行相应的处理,最终得到解码后的字符串。
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param s string字符串 # @return string字符串 # class Solution: def decodeString(self , s: str) -> str: stack = [] curr_str = "" # 当前要重复的字符串 curr_num = 0 # 当前重复次数 for c in s: if c.isdigit(): curr_num = curr_num * 10 + int(c) elif c == "[": stack.append(curr_str) stack.append(curr_num) curr_str = "" curr_num = 0 elif c == "]": num = stack.pop() # 弹出前面的重复次数 prev_str = stack.pop() # 弹出前面的字符串 curr_str = prev_str + num * curr_str else: curr_str += c return curr_str
在 decodeString
函数中,我们维护了一个栈 stack
,用来存储需要重复的字符串和重复次数。通过遍历输入字符串 s
,对每个字符进行处理:
- 如果是数字,则将其加入当前重复次数
curr_num
中; - 如果是左括号
[
,则将当前重复次数和当前要重复的字符串入栈,并重置curr_num
和curr_str
防止重复次数和字符串串联; - 如果是右括号
]
,则从栈中弹出前面的重复次数和字符串,将当前重复的字符串curr_str
加上之前的字符串prev_str
乘以前面的重复次数num
,得到新的重复字符串; - 否则,将当前字符加入当前重复的字符串
curr_str
中。
最后,返回得到的解码字符串 curr_str
即可。