LeetCode 394 [Decode String]

原题

给一段string，解码

样例

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

解题思路

• 一个stack记录倍数
• 一个stack记录string
• 遇到"["添加倍数(因为倍数可能是“123”...), 遇到"]"弹出一段string乘以倍数，再压入栈

完整代码

class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return ""
    
        digit = []
        string = []
        temp_digit = ""
        for char in s:
            if char.isdigit():
                temp_digit += char
            elif char == "[":
                digit.append(int(temp_digit))
                string.append(char)
                temp_digit = ""
            elif char == "]":
                cur = []
                temp = string.pop() 
                while string and temp != "[":
                    cur.insert(0, temp)
                    temp = string.pop()
                for i in range(digit.pop()):
                    string += cur
            else:
                string.append(char)
        return "".join(string)