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

实现结果

总结

• 本题中比较难处理的是括号内嵌的问题，这里要从内部往外扩展，这里符合栈先入后出的特性，所以采用栈的思路来解决此问题。
• 构建辅助栈，每项存储两个信息，一个左括号前面的字符，一个左括号前面的数值
• 遍历字符串，对不同的情况进行相应的处理：
  • 遍历元素为数字字符时，转换为数值，用于后续倍数计算（这里要注意数字位数，不一定只有个位数数字）
  • 遍历元素为字母时，添加到结果末尾
  • 遍历元素为左括号时，进行入栈操作，将左括号前面的字符和数字压入栈中，同时要重置存储这两项的变量
  • 遍历元素为右括号时，开始出栈，同时拼接字符。