字符串解码

🎯 问题描述（来源于LeetCode）

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

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

测试用例保证输出的长度不会超过 105。
说明：

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

示例：

  • 示例 1：
1
2
输入：s = "3[a]2[bc]"
输出："aaabcbc"
  • 示例 2：
1
2
输入：s = "3[a2[c]]"
输出："accaccacc"

💻 解题思路

思路1：栈

思路1：代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def decodeString(self, s: str) -> str:
        result=[]
        for x in s:
            if x !=']':
                result.append(x)
                continue
            sub=''
            while result[-1]!='[':
                sub=result.pop()+sub
            result.pop()
            k,base=0,1
            while result and result[-1].isdigit():
                k+=int(result.pop())*base
                base*=10
            result.append(sub*k)
        return ''.join(result)

思路1：📊 性能分析

提交结果
  • 运行时间：0ms击败100.00%
  • 内存消耗：19.15MB击败39.06%
复杂度验证
  • 时间复杂度：O(N)O(N)
  • 空间复杂度：O(N)O(N)

思考