# NO STACK, O(n) recursive solution in Python

• ``````def helper(s):
res = ""
while s:
num = ""
while s and s[-1] in '0123456789':
num += s.pop()
if num:
num = int(num)
s.pop()
res += helper(s) * num
else:
c = s.pop()
if c not in "[]":
res += c
if c == ']':
break
return res

class Solution(object):
def decodeString(self, s):
return helper(list(s)[::-1])
``````

• It is unnecessary to check while(s) inside the while loop when iterating through the numbers. We are guaranteed valid input. Accepts fine without it.

def helper(s):
res = ""
while s:
num = ""
while s and s[-1] in '0123456789':
num += s.pop()
if num:
num = int(num)
s.pop()
res += helper(s) * num
else:
c = s.pop()
if c not in "[]":
res += c
if c == ']':
break
return res

class Solution(object):
def decodeString(self, s):
return helper(list(s)[::-1])

• my solution no stack, only use find
idea:
find the first ']',it's index is right
find the '[' called left which is the fist '[' before the first ']'

than s = some_words_before + 'digit[words]' + some_words_after_with out_ [
can become
s = some_words_before + digit * words + some_words_after_with out_ [
repeat the steps while there is not [ in s

``````class Solution(object):
def decodeString(self, s):
"""
:type s: str
:rtype: str
"""
right = s.find(']')
left = s[:right][::-1].find('[')
while left > 0:
startnum = right - left - 2
while startnum > 0 and s[startnum].isdigit():
startnum -= 1
startnum = startnum + 1 if startnum > 0 else startnum
s = s[:startnum] + int(s[startnum:(right - left - 1)])*s[(right - left):right] + s[(right + 1):]
right = s.find(']')
left = s[:right][::-1].find('[')
return s

``````

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