394. Decode String

问题描述

Given an encoded string, return it's decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

Examples:
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

思路

用一个stack，存放[times, substring]的组合
用for loop过一遍，如果是数字，则一定是某个string或者string组合前面的倍数
[ 出现，说明有新的substring，初始化后加入stack
] 出现，说明可以完成与最后的[组合string，计算完成后加入上级[中的string里

def decodeString(s):
    """
    :type s: str
    :rtype: str
    """
    stack = []
    num = tmp = ""
    stack.append([1, tmp])
    for i in s:
        if i.isdigit():
            num += i
        elif i == "[":
            stack.append([int(num), tmp])
            num = ''
        elif i == "]":
            times, str = stack.pop()
            stack[-1][1] += str*times
        else:
            stack[-1][1] += i
        print(stack)
    return stack[0][1]