394. 字符串解码（Python）

题目

难度：★★★☆☆
类型：字符串
方法：栈

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: 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"

解答

字符串的编解码常常需要用到栈的数据结构，其核心在于，从最内层开始，逐层解码，嵌套是这个问题的一大难点。选择合适的数据结构并用于解决这个问题，问题就解决了一半。

我们将该问题中的输入编码字符看做由重复项和重复数按照一定编排方式构成的序列，重复项就是方括号里面的内容，重复数就是方括号之前的数字。

具体流程是：从第一个字符开始，逐个入栈，遇到“]”时，开始出栈并查看出栈的元素，直到第一次遇到“[”，这两个括号一定是匹配的，中间包含的就是重复项。然后继续出栈，将重复数取出来，与刚刚计算好的重复项一同把这一层做解码，再次将解码后的字符串入栈。最后，栈里一定是不包含数字和括号的字符串，连接起来就是解码的结果。

这道题的另一个难点是，寻找解码边界。因为重复项和重复次数不一定只由一个字符组成，所以需要用循环遍历并及时判断的方式来寻找边界。

class Solution:
    def decodeString(self, s: str) -> str:

        stack = []

        for c in s:
            if c == ']':

                # 计算重复元素
                repeat_word = ''
                while True:
                    e = stack.pop()
                    if e == '[':
                        break
                    repeat_word = e + repeat_word

                # 计算重复次数
                repeat_num = ''
                while True:
                    e = stack.pop() if stack else ''
                    if not e.isdigit():
                        stack.append(e)
                        break
                    repeat_num = e + repeat_num

                sub_str = repeat_word * int(repeat_num)
                for _ in sub_str:
                    stack.append(_)
            else:
                stack.append(c)
        return ''.join(stack)

当然，也可以用python中的正则表达式实现上面的操作（逐层替换），真的很香。

import re
class Solution(object):
    def decodeString(self, s):
        while '[' in s:
            s = re.sub(r'(\d+)\[([A-Za-z]*)\]', lambda m:int(m.group(1)) * m.group(2), s)
        return s

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析