LeetCode Solutions Blog

Mini Parser

Number: 385

Difficulty: Medium

Paid? No

Problem Description

Given a string s representing the serialization of a nested list (where each element is either an integer or a list of integers/lists), deserialize s and return the corresponding NestedInteger object.

Key Insights

Use a stack to manage the nested levels in the input string.
If the string does not start with a '[', it represents a single integer.
When encountering '[', create a new NestedInteger and push it onto the stack.
When encountering digits (or a '-' sign), build the integer value.
When a comma or ']' is reached, if an integer is being accumulated, add it to the current NestedInteger.
When encountering ']', complete the current NestedInteger and attach it to the one on top of the stack (if any).

Space and Time Complexity

Time Complexity: O(n) – we traverse each character in the input string once.
Space Complexity: O(n) – in the worst case, the stack can grow proportionally to the nested depth of the input.

Solution

The solution uses a stack-based approach:

If the input string is a plain number, return a NestedInteger with that single value.
For nested lists, iterate through the string:
- On encountering '[', push a new empty NestedInteger onto the stack.
- Accumulate numeric characters (considering '-' for negative numbers) to form an integer.
- On encountering a comma or ']', if a number was being built, convert it to an integer and add it to the NestedInteger on top of the stack.
- When a ']' is encountered, pop the NestedInteger from the stack and add it to the NestedInteger now at the top (unless it is the last element).
After processing the entire string, the NestedInteger remaining on the stack is the result.

Code Solutions

# Definition for a NestedInteger.
class NestedInteger:
    def __init__(self, value=None):
        # If value is None, initialize an empty list. Otherwise, store a single integer.
        if value is None:
            self._list = []
            self._integer = None
        else:
            self._list = None
            self._integer = value

    def isInteger(self):
        return self._integer is not None

    def add(self, elem):
        if self._list is None:
            self._list = []
        self._list.append(elem)

    def setInteger(self, value):
        self._integer = value
        self._list = None

    def getInteger(self):
        return self._integer

    def getList(self):
        return self._list

def deserialize(s: str) -> NestedInteger:
    # Base case: if the string does not start with '[', it is a single integer.
    if s[0] != '[':
        return NestedInteger(int(s))
    
    stack = []
    num = ""
    negative = False

    # Traverse each character in the string.
    for ch in s:
        if ch == '[':  # Start a new NestedInteger list.
            stack.append(NestedInteger())
        elif ch == ']':
            # If finishing a number before the closing bracket.
            if num:
                value = -int(num) if negative else int(num)
                stack[-1].add(NestedInteger(value))
                num = ""
                negative = False
            # If there is a NestedInteger on the stack, pop and add it to the previous one.
            if len(stack) > 1:
                ni = stack.pop()
                stack[-1].add(ni)
        elif ch == ',':
            # Add number if it was built before the comma.
            if num:
                value = -int(num) if negative else int(num)
                stack[-1].add(NestedInteger(value))
                num = ""
                negative = False
        elif ch == '-':
            negative = True
        else:
            # Accumulate digit characters.
            num += ch

    return stack[0]