Python solution: recursion and stack


  • 0
    T
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        return self.dfs(s)
    
    def dfs(self,s):
        if s.isalpha():
            return s
        res = ""
        stack = []
        for i in range(len(s)):
            if not stack and s[i].isalpha():
                res += s[i]
            if s[i]=='[':
                stack.append(i)
            if s[i]==']':
                left = stack.pop()
                if not stack:
                    num_start = left-1
                    while s[num_start].isdigit(): num_start -= 1
                    repeat = int(s[num_start+1:left])
                    res += repeat*self.dfs(s[left+1:i])
        return res

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.