https://leetcode.com/problems/decode-string

For me it was not medium problem, more like hard, I am not very good at all these parser problems. However if you spend some time on this problem, logic will be not very difficult. The idea is to read symbol by symbol and check options:

  1. If we see digit, it means that we need to form number, so just do it: multiply already formed number by 10 and add this digit.
  2. If we see open bracket [, it means, that we just right before finished to form our number: so we put it into our stack. Also we put in our stack empty string.
  3. If we have close bracket ], it means that we just finished [...] block and what we have in our stack: on the top it is solution for what we have inside bracktes, before we have number of repetitions of this string rep and finally, before we have string built previously: so we concatenate str2 and str1 * rep.
  4. Finally, if we have some other symbol, that is letter, we add it the the last element of our stack.

For better understanding the process, let us consider example s = 3[a5[c]]4[b]:

  1. [''] at first we have stack with empty string.
  2. ['', 3, ''], open bracket: now we have stack with 3 elements: empty string, number 3 and empty string.
  3. ['', 3, 'a']: build our string
  4. ['', 3, 'a', 5, ''], open bracket: add number and empty string
  5. ['', 3, 'a', 5, 'c'] build string
  6. ['', 3, 'accccc'] : now we have closing bracket, so we remove last 3 elements and put accccc into our stack
  7. ['acccccacccccaccccc'] we again have closing bracket, so we remove last 3 elements and put new one.
  8. ['acccccacccccaccccc', 4, '']: open bracket, add number and empty string to stack
  9. ['acccccacccccaccccc', 4, 'b'] build string
  10. ['acccccacccccacccccbbbb'] closing bracket: remove last 3 elements and put one new.

Finally, return joined strings from our stack.

Complexity: we can say, that time and space complexity is O(m), where m is size of our answer. Potentially it can be very big, for strings like 999999999999999[a], but I do not think leetcode will have such tests.

class Solution:
    def decodeString(self, s):
        it, num, stack = 0, 0, [""]
        while it < len(s):
            if s[it].isdigit():
                num = num * 10 + int(s[it])
            elif s[it] == "[":
                stack.append(num)
                num = 0
                stack.append("")
            elif s[it] == "]":
                str1 = stack.pop()
                rep = stack.pop()
                str2 = stack.pop()
                stack.append(str2 + str1 * rep)
            else:
                stack[-1] += s[it]              
            it += 1           
        return "".join(stack)

If you like the solution, you can upvote it on leetcode discussion section: Problem 0394