题目

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

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

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

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

示例:

1
2
3
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

题解

思路

  • 这题烦就烦在它的括号是可以嵌套的
  • 括号嵌套就想到了栈
  • 我们在栈stack里存元祖，信息是“当前的字符串this_str”和“这个字符串要重复的次数num”。
  • 遍历str
  • 首先考虑简单的情况
    • 如果字符是数字，那么加到num上，注意字符和数字之间的转换。
    • 如果字符是字符，那么加到this_str里
  • 接着要考虑括号的开闭
    • 如果遇到了开括号，那么将当前读到的字符串（上层到这个中括号内的字符串）和要重复的次数（这层的中括号内要重复的次数）入栈，同时将this_str和num清空，以便进入下一层。比如说3[5[a]]，读到里面的中括号时，入栈的num是5。
    • 如果遇到了闭括号，那么从栈取出一项元祖，记last_str和this_num，此时的this_str是这层的字符，而this_num是这层需要的重复次数。最后将this_str重复响应次数后和之前的last_str结合。
  • 括号的内容有点复杂，要捋一捋。
  • 要知道this_str是会不断变大的，每次清空它前都把它状态放到stack里了。相当于一个带着两百块钱的没有资产的赌徒，但是他特厉害，每天赌博都能赢。这个this_str有时表示赌徒手上拿的现金，那么每天都会清零（清为200，准确地说）。表示总资产的时候，就是每天扩大。为什么有时表示每天的资产，有时表示总资产？就相当于每天的资产是总资产的中括号内。深入到中括号内部的时候就清零了，再中括号外部的时候，就是总资产了。当然中括号外部可能还有中括号。不知道这么说会不会更好理解？

执行结果：通过
执行用时 :40 ms, 在所有 Python3 提交中击败了95.51%的用户
内存消耗 :13.6 MB, 在所有 Python3 提交中击败了5.26%的用户

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def decodeString(self, s: str) -> str:       
        stack, this_str,num = [], '', 0
        for i in s:
            if i.isdigit():num = num * 10 + int(i)
            elif i.isalpha():this_str += i
            elif i == '[':
                stack.append((this_str,num))
                this_str, num = '', 0
            else: # i == ']'
                last_str, this_num = stack.pop()
                this_str = last_str + this_num * this_str
        return this_str

复杂度分析

  • 时间复杂度 O(N)O(N)，遍历了一遍字符串
  • 空间复杂度 O(N)O(N)，需要一个额外的栈