Easy to understand python solution using Stack


  • 0
    F

    Farily simple solution, if we meet a digit, find the whole digit and append it into nums, if we meet an alphabet, find the whole alpha string and append it into c. When we encoutner ']', simply pop from both array, and multiply them and push it back into c. And after that, check the length of both array, if the level is 0, then add it to the result, else combine the last two string in c.

    class Solution(object):
        def decodeString(self, s):
            """
            :type s: str
            :rtype: str
            """
            nums = []
            c = []
            i = 0
            r = ''
            n = len(s)
            level = 0
            while i < n:
                if s[i].isdigit():
                    j = i+1
                    while j < n and s[j].isdigit():
                        j += 1
                    nums.append(s[i:j])
                    i = j
                elif s[i].isalpha():
                    j = i+1
                    while j < n and s[j].isalpha():
                        j += 1
                    c.append(s[i:j])
                    i = j
                elif s[i] == '[':
                    i += 1
                    level += 1
                elif s[i] == ']':
                    c.append(c.pop()*int(nums.pop()))
                    i += 1
                    level -= 1
                if len(c) > len(nums):
                    if level == 0:
                        r += c.pop()
                    else:
                        a = c.pop()
                        c.append(c.pop()+a)
            return r
    

Log in to reply
 

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