Python recursive solution


  • 1
    N

    A python recursive solution:
    First, determine the type of parsing: two scenarios can be met:

    1. the first character of a given string is '[': to parse a list.
      Whenever '[' is met, start parsing a list and end when ']' is met.
    2. otherwise: to parse a simple integer.
      The recursive function should return the parsed result and the ending index of the subproblem or equivalently the start index of the next parsing task.
    def deserialize(self, s):
            """
            :type s: str
            :rtype: NestedInteger
            """
            parsed, _ = self.helper(s, 0)
            return parsed
    
        def helper(self, s, ind):
            i = ind
            # scenario 1: to parse a nested list
            if s[i] == '[':
                parsed = NestedInteger()
                i += 1
                while i < len(s):
                    if s[i] == ']':
                        return parsed, i+1
                    if s[i] == '[':
                        nested, i = self.helper(s, i)
                        parsed.add(nested)
                    elif s[i] in '-0123456789':
                        ele, i = self.helper(s, i)
                        parsed.add(ele)
                   # put this case at the bottom so that we don't need list all the spaces (e.g. space, tab) or comma separator
                    else:
                        i += 1
           # scenario 2: to parse an integer
            else:
                temp = i
                while temp < len(s) and s[temp] in '-0123456789':
                    temp += 1
                return NestedInteger(int(s[i:temp])), temp
    

  • 0

    This code is super clear.


Log in to reply
 

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