NO STACK, O(n) recursive solution in Python


  • 4
    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])
    

  • 0
    A

    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.

    @agave said in 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])


  • 0
    L

    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
                
    

Log in to reply
 

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