394. 字符串解码
题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/decode-string
题目
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例:
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
解题思路
思路：栈
在上面的例子中，第二个示例出现了括号内嵌的情况。本题中，比较难处理的也是这部分。
在本篇幅中，我们使用栈的思路，来解决本题。上面提及出现的括号内嵌的情况，当我们返回的时候，要从内部往外去生成与拼接字符，这也是我们使用栈的原因，因为栈具有先入后出的特性。
在这里，我们栈里面，每项需要存储两个信息，一个是左括号前面的字符，一个是左括号前面的数字。
例如示例 2，3[a2[c]]，其中 a2[c] 这一部分，入栈时应该是这样的：('a', 2)，后面会遍历字符 c，遇到右括号的时候，要进行出栈操作。弹出的元素 ('a', 2)，这里要跟字符 c 拼接称新的字符串 a + 2 * 'c'，也就是 acc。
具体的做法：
- 遍历元素为数字时，将数字字符转换为数字，这里用于后面字符解码倍数运算；
- 遍历元素为字母时，这个时候，直接将字符加在结果尾部；
- 遍历元素为左括号时，要将左括号前面的字母和数字进行入栈，入栈之后，要将存储这两项的变量重置；
- 遍历元素为右括号时，进行出栈，拼接字符。
算法实现过程的图解如下：
图解
具体的代码实现如下。
代码实现
class Solution:
def decodeString(self, s: str) -> str:
# 辅助栈，每项存储两个信息，一个左括号前面的字符，一个左括号前面的数字
stack = []
mult = 0
ans = ''
for char in s:
# 当字符为数字字符时，转换为数值，用于后续倍数运算
if char.isdigit():
# mult = int(char)
# 这里要注意数字位数，
# 上面的写法，遇到用例 "100[leetcode]" 出错了，这里改为
mult = mult * 10 + int(char)
# 遇到左括号时，将前面的字符和数值入栈
elif char == '[':
stack.append((ans, mult))
# 这里要重置存储这两项的变量
ans = ''
mult = 0
# 遇到右括号时，出栈
elif char == ']':
front_char, cur_mult = stack.pop()
ans = front_char + cur_mult * ans
# 这里表示遇到的是字符，直接添加到 ans 末尾
else:
ans += char
return ans
实现结果
实现结果
总结
- 本题中比较难处理的是括号内嵌的问题，这里要从内部往外扩展，这里符合栈先入后出的特性，所以采用栈的思路来解决此问题。
- 构建辅助栈，每项存储两个信息，一个左括号前面的字符，一个左括号前面的数值
- 遍历字符串，对不同的情况进行相应的处理：
- 遍历元素为数字字符时，转换为数值，用于后续倍数计算（这里要注意数字位数，不一定只有个位数数字）
- 遍历元素为字母时，添加到结果末尾
- 遍历元素为左括号时，进行入栈操作，将左括号前面的字符和数字压入栈中，同时要重置存储这两项的变量
- 遍历元素为右括号时，开始出栈，同时拼接字符。
欢迎关注微信公众号《书所集录》
网友评论