SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

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<NestedInteger> &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<NestedInteger> 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<Object> list = new ArrayList<>();
            int start = 1, depth = 0;
            for (int i = 1; i < s.length(); i++) {
                if (s.charAt(i) == '[') depth++;
                else if (s.charAt(i) == ']') depth--;
                else if (s.charAt(i) == ',' && depth == 0) {
                    list.add(parse(s.substring(start, i)));
                    start = i + 1;
                }
            }
            if (start < s.length() - 1) list.add(parse(s.substring(start, s.length() - 1)));
            return list;
        } else {
            return Integer.parseInt(s);
        }
    }

    private NestedInteger dfs(Object input) {
        if (input instanceof Integer) {
            return new NestedInteger((int) input);
        }
        NestedInteger ni = new NestedInteger();
        for (Object obj : (List<Object>) input) {
            ni.add(dfs(obj));
        }
        return ni;
    }
}

JavaScript

/**
 * @param {string} s
 * @return {NestedInteger}
 */
const deserialize = (s) => {
    let a = JSON.parse(s);
    return dfs(a);
};

const dfs = (input) => {
    if (Number.isInteger(input)) return new NestedInteger(input); // if (!Array.isArray(input)) return new NestedInteger(input); also works
    let l = new NestedInteger();
    for (const e of input) l.add(dfs(e));
    return l;
};