LeetCode Solutions Blog

Mini Parser

Difficulty: Medium

Problem Description

Given a string s that represents the serialization of a nested list, implement a parser to deserialize it and return the deserialized NestedInteger. Each element is either an integer or a list whose elements may also be integers or other lists.

Key Insights

The input string can contain integers, square brackets for lists, commas, and negative signs.
Nested structures need to be handled recursively or using a stack to maintain the current state of parsing.
Each time a new integer or list is encountered, it must be correctly added to the current NestedInteger structure.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string, since each character is processed once. Space Complexity: O(n), in the worst case, for the stack or recursion call stack used to handle nested lists.

Solution

To solve this problem, we utilize a stack to handle the nested structure of the input string. As we iterate through the characters in the string, we manage the current state of parsing using the stack. When encountering integers, we create a NestedInteger object and push it onto the stack. When encountering an opening bracket '[', we start a new list, and upon encountering a closing bracket ']', we pop from the stack to form the current list. This approach allows us to maintain the hierarchical structure of the input.

Code Solutions

class NestedInteger:
    def __init__(self, value=None):
        if value is not None:
            self._integer = value
            self._list = None
        else:
            self._integer = None
            self._list = []

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

    def add(self, elem):
        self._list.append(elem)

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

    def getInteger(self):
        return self._integer

    def getList(self):
        return self._list

def deserialize(s: str) -> NestedInteger:
    stack = []
    current = NestedInteger()
    num = 0
    negative = False

    for i in range(len(s)):
        char = s[i]
        
        if char == '[':
            # Push the current NestedInteger onto the stack
            stack.append(current)
            current = NestedInteger()  # Start a new NestedInteger

        elif char == ']':
            if s[i-1].isdigit() or s[i-1] == '-':
                current.add(NestedInteger(num if not negative else -num))
                num = 0
                negative = False
            # Pop from the stack and add the current list to it
            top = stack.pop()
            top.add(current)
            current = top  # Back to the previous NestedInteger

        elif char == ',':
            if s[i-1].isdigit() or s[i-1] == '-':
                current.add(NestedInteger(num if not negative else -num))
                num = 0
                negative = False

        elif char.isdigit():
            num = num * 10 + int(char)

        elif char == '-':
            negative = True

    if num or negative:
        current.add(NestedInteger(num if not negative else -num))

    return current