385. Mini Parser

Description

The problem involves deserializing a string that represents nested integers. The string can contain integers or lists of integers, and the goal is to convert it into a data structure that represents this hierarchy. The structure should allow distinguishing between single integers and nested lists of integers.

Intuition

The problem can be approached using recursive parsing. When encountering a list (represented by [ and ]), the idea is to recursively process its elements. When encountering an integer, it can be directly processed. Recursion naturally helps with handling nested structures of arbitrary depth.

Approach

1. Use a recursive function parse to handle both lists and integers.
2. If a list is detected (starting with [), create a new NestedInteger object and recursively add elements to it until the closing ] is found.
3. If a number is detected, directly return a NestedInteger object holding the number.
4. The main deserialize function initializes the parsing by checking the input string and then recursively processes it using the parse function.

Complexity

Time Complexity:

O(n), where n is the length of the input string. Each character in the string is processed once.

Space Complexity:

O(n) for the recursive call stack and the space needed to store the parsed NestedInteger structure.

Code

C++

// Assuming the NestedInteger class is defined like this:
// class NestedInteger {
// public:
//     NestedInteger() {};                     // Initializes an empty list
//     NestedInteger(int value) {};            // Initializes a single integer
//     bool isInteger() const;                 // Returns true if this NestedInteger holds a single integer
//     int getInteger() const;                 // Returns the single integer that this NestedInteger holds
//     void setInteger(int value);             // Set this NestedInteger to hold a single integer
//     void add(const NestedInteger &ni);      // Adds a NestedInteger element to this NestedInteger
//     const std::vector &getList() const; // Returns the nested list
// };

class Solution {
public:
    NestedInteger deserialize(const std::string &s) {
        std::istringstream iss(s);
        return parse(iss);
    }

private:
    NestedInteger parse(std::istringstream &iss) {
        if (iss.peek() == '[') {
            iss.get(); // Skip '['
            NestedInteger ni;
            while (iss.peek() != ']') {
                ni.add(parse(iss));
                if (iss.peek() == ',') {
                    iss.get(); // Skip ','
                }
            }
            iss.get(); // Skip ']'
            return ni;
        } else {
            int num;
            iss >> num;
            return NestedInteger(num);
        }
    }
};

Python

# Assuming NestedInteger class is already defined with the following methods:
# - NestedInteger() initializes an empty nested list.
# - NestedInteger(int value) initializes a single integer.
# - void add(NestedInteger ni) adds a NestedInteger element to this NestedInteger.
# - bool isInteger() returns true if this NestedInteger holds a single integer.
# - int getInteger() returns the single integer that this NestedInteger holds, if it holds a single integer.
# - List[NestedInteger] getList() returns the nested list that this NestedInteger holds, if it holds a nested list.

class Solution:
    def deserialize(self, s: str) -> NestedInteger:
        a = json.loads(s)
        return self.dfs(a)

    def dfs(self, input) -> NestedInteger:
        if isinstance(input, int):
            return NestedInteger(input)
        l = NestedInteger()
        for e in input:
            l.add(self.dfs(e))
        return l

Java

// Assuming NestedInteger class is already defined with the following methods:
// - NestedInteger() initializes an empty nested list.
// - NestedInteger(int value) initializes a single integer.
// - void add(NestedInteger ni) adds a NestedInteger element to this NestedInteger.
// - boolean isInteger() returns true if this NestedInteger holds a single integer.
// - Integer getInteger() returns the single integer that this NestedInteger holds, if it holds a single integer.
// - List getList() returns the nested list that this NestedInteger holds, if it holds a nested list.

public class Solution {
    public NestedInteger deserialize(String s) {
        Object parsed = parse(s);
        return dfs(parsed);
    }

    private Object parse(String s) {
        if (s.charAt(0) == '[') {
            List