
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
- Use a recursive function
parse
to handle both lists and integers. - If a list is detected (starting with
[
), create a newNestedInteger
object and recursively add elements to it until the closing]
is found. - If a number is detected, directly return a
NestedInteger
object holding the number. - The main
deserialize
function initializes the parsing by checking the input string and then recursively processes it using theparse
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
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;
};