394. 字符串解码 · Algorithm Lab

给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。测试用例保证输出的长度不会超过 105。

示例 1：

输入： s = "3a2bc" 输出："aaabcbc"

示例 2：

输入： s = "3a2c" 输出："accaccacc"

示例 3：

输入： s = "2abc3cdef" 输出："abcabccdcdcdef"

示例 4：

输入： s = "abc3cdxyz" 输出："abccdcdcdxyz"

提示：

1 <= s.length <= 30
s 由小写英文字母、数字和方括号 '[]' 组成
s 保证是一个有效的输入。
s 中所有整数的取值范围为 [1, 300]

参考解法

下面保留的是原始练习仓库中的个人作答，可在右侧工作台中独立重写，再按需揭示对照。

python


class Solution(object):
    def decodeString(self, s):
        stack = []
        result = ''
        current_num = 0  # 用于存储累计数字（多位数） 
        
        for char in s:
            if char.isdigit():
                current_num = current_num * 10 + int(char)
            elif char == '[':
                # 左括号，当前数字和之前的字符串入栈然后重置
                stack.append((result, current_num))
                result = ''
                current_num = 0
            elif char == ']':
                # 右括号，弹出栈顶的（前缀字符串/重复次数），拼接结果
                prev_str, num = stack.pop()
                result = prev_str + num * result
            else:
                result += char  # 普通字符直接拼接
        return result
        """
        :type s: str
        :rtype: str
        """