Simple recursive solution in python


  • 0
    I

    I think that recursion is naturally the most intuitive way to do this question.
    If i see some strnig like 3[whatever], naturally i want to recursively decode whatever is inside the brackets, and then just multiply it by 3. This is what my solution does below. Not very fast percentile wise, but I think this is a very intuitive, easy to code approach you can give in a interview:

    
    class Solution(object):
        def decode_util(self, s, start):
            i = start
            curr_num = 0
            curr_str = ''
            
            while i < len(s):
                if s[i].isdigit():
                    curr_num *= 10
                    curr_num += int(s[i])
                    i += 1
                elif s[i] in lowercase:
                    curr_str += s[i]
                    i += 1
                elif s[i] == '[':
                    bracket_decode, last_idx = self.decode_util(s, i+1)
                    curr_str += (curr_num * bracket_decode)
                    i = last_idx + 1
                    curr_num = 0
                elif s[i] == ']':
                    break
                
            return curr_str, i
                    
        
        def decodeString(self, s):
            """
            :type s: str
            :rtype: str
            """
            return self.decode_util(s, 0)[0]

Log in to reply
 

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