#recursion

#the main idea is to only calculate the mosr outer layer. (which is when stack is empty.)

#we put all the inner layer to another `decodeString()` to get its value.

#time: O(N), N is the length of the string.

#space: O(N).

class Solution(object):

def decodeString(self, s):

opt = ''

k = ''

stack = []

for i, c in enumerate(s):

if c=='[':

stack.append(i)

elif c==']':

i_start = stack.pop()

if not stack:

opt += int(k)*self.decodeString(s[i_start+1:i])

k = ''

elif c.isdigit() and not stack:

k+=c

elif not stack:

opt+=c

return opt or s

#stack

#as we iterate the string, we will dive into different level of brackets.

#we store the value of the current level in the `opt`

#and store the outer level in the stack

#when we get out of this level, we calculate the value.

#time: O(N), N is the length of the string.

#space: O(N).

class Solution(object):

def decodeString(self, s):

opt = ''

stack = []

k = ''

for c in s:

if c=='[':

stack.append(opt)

stack.append(k)

opt = ''

k = ''

elif c==']':

n = stack.pop()

pre = stack.pop()

opt = pre+int(n)*opt

elif c.isdigit():

k+=c

else:

opt+=c

return opt