algoadvance

Given a nested list of integers represented as a string, implement a parser to deserialize it into a NestedInteger object.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

Example:

  1. Given s = "324", you should return a NestedInteger object which contains a single integer 324.
  2. Given s = "[123,[456,[789]]]", you should return a NestedInteger object containing a nested list with integers 123, 456 and 789.

Clarifying Questions

  1. What is a NestedInteger object?

    A NestedInteger object is a recursive structure that can represent either a single integer or a list of NestedInteger objects. It typically has methods such as isInteger, getInteger, setInteger, add, and getList.

  2. How should nested lists be handled?

    Nested lists should be parsed recursively. We will use a stack to handle the recursive structure and to build the nested list.

  3. What are the edge cases?

    • Empty string: not applicable since string is non-empty by assumption.
    • Single integer without nesting.
    • Deeply nested structures.

Strategy

  1. Initialization and Base Case: If the string represents a single integer, directly return it as a NestedInteger.

  2. Stack-Based Parsing: Use a stack to parse through the string:
    • When encountering a [, push a new NestedInteger to the stack.
    • When encountering a ], pop the top NestedInteger from the stack and add it to the NestedInteger that is now on top of the stack.
    • Keep track of numbers and negative signs.
  3. Character Handling:
    • Numbers and - signs will form integers.
    • [ will start a new list.
    • ] will end the current nested list.
    • , will separate elements in the list (used to identify termination of an integer).

Code

Here’s the complete code implementing the above strategy:

class NestedInteger:
    def __init__(self, value=None):
        self.value = value
        self.list = []
    
    def isInteger(self):
        return self.value is not None
    
    def getInteger(self):
        return self.value
    
    def setInteger(self, value):
        self.value = value
    
    def add(self, elem):
        self.list.append(elem)
    
    def getList(self):
        return self.list

def deserialize(s: str) -> NestedInteger:
    if not s:
        return NestedInteger()
    
    if s[0] != '[':
        return NestedInteger(int(s))
    
    stack = []
    num, negative = None, False
    
    for i in range(len(s)):
        ch = s[i]
        
        if ch == '-':
            negative = True
        elif ch.isdigit():
            if num is None:
                num = 0
            num = num * 10 + int(ch)
        elif ch == '[':
            stack.append(NestedInteger())
        elif ch in ',]':
            if num is not None:
                if negative:
                    num = -num
                stack[-1].add(NestedInteger(num))
            num, negative = None, False
            
            if ch == ']' and len(stack) > 1:
                last = stack.pop()
                stack[-1].add(last)
    
    return stack[0]

# Example usage:
# s = "[123,[456,[789]]]"
# result = deserialize(s)
# The result object will be a NestedInteger representing the nested structure.

Time Complexity

The time complexity of this solution is O(n), where n is the length of the string s. Each character in the string is processed exactly once.

Try our interview co-pilot at AlgoAdvance.com