394. Decode String - Google Amazon Bloomberg Oracle

題目來自Leetcode

題目

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]. s = “3[a]2[bc]“, return “aaabcbc”. s = “3[a2[c]]“, return “accaccacc”. s = “2[abc]3[cd]ef”, return “abcabccdcdcdef”.

stack想法：

1. stack用來存數字、[、以及當有上引號存在stack中時就存英文字母，否則就把英文字母存在結果字串就好
2. 當loop到數字時，因為數字可能有好幾個位數，所以先用變數去存，當碰到 ‘[’ 時，再把數字先存到stack，接著也存’[‘， 記得將用來存數字的變數清空
3. 當碰到 ‘]’ 時，開始將括號裡的內容物也就是存在stack的東西pop出來 直到碰到 ‘[’ 為止，將 ‘[’ 前面跟的數字對目前引號提出的字母做乘積，做完後由於可能是巢狀結構，像是範例二，所以當stack還有 ‘[’ 表示是巢狀結構，就要再把目前做完的字母丟回stack，沒有的話就接到結果字串後面

Code

def decodeString(self, s):
    """
    :type s: str
    :rtype: str
    """
    if not s: return ""
    
    stack, res = [], ""
    nums = ""
    for char in s:
        if char.isdigit():
            nums += char
        elif char == "[":
            stack.append(nums)
            stack.append(char)
            nums = ""
        elif "[" in stack and char.isalpha():
            stack.append(char)
        elif char == "]":
            current = ""
            # tackle the char in []
            while stack[-1] != "[":
                current = stack.pop() + current
            stack.pop() # pop out [
            
            current *= int(stack.pop())
            # if still has [ in stack, then push back the current chars in stack
            if "[" in stack:
                stack.extend(current[:])
            else:
                res += current
        else:
            res += char
    return res