大廠面試真題詳解：字元串解碼

給出一個表達式 s，此表達式包括數字，字母以及方括号。在方括号前的數字表示方括号内容的重複次數(括号内的内容可以是字元串或另一個表達式)，請将這個表達式展開成一個字元串。

線上評測位址：

領扣題庫官網 樣例1

輸入: S = abc3[a]
輸出: "abcaaa"           

樣例2

輸入: S = 3[2[ad]3[pf]]xyz
輸出: "adadpfpfpfadadpfpfpfadadpfpfpfxyz"           

題解

把所有字元一個個放到 stack 裡， 如果碰到了 ]，就從 stack 找到對應的字元串和重複次數，decode 之後再放回 stack 裡。

class Solution:
    """
    @param s: an expression includes numbers, letters and brackets
    @return: a string
    """
    def expressionExpand(self, s):
        stack = []
        for c in s:
            if c != ']':
                stack.append(c)
                continue
                
            strs = []
            while stack and stack[-1] != '[':
                strs.append(stack.pop())
            
            # skip '['
            stack.pop()
            
            repeats = 0
            base = 1
            while stack and stack[-1].isdigit():
                repeats += (ord(stack.pop()) - ord('0')) * base
                base *= 10
            stack.append(''.join(reversed(strs)) * repeats)
        
        return ''.join(stack)           

更多題解參考：

九章官網solution