Description
Given a string s 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.
Examples:
Example 1:
Input: s = "324"
Output: 324
Explanation: You should return a NestedInteger object which contains a single integer 324.
Example 2:
Input: s = "[123,[456,[789]]]"
Output: [123,[456,[789]]]
Explanation: Return a NestedInteger object containing a nested list with 2 elements:
1. An integer containing value 123.
2. A nested list containing two elements:
i. An integer containing value 456.
ii. A nested list with one element:
a. An integer containing value 789Solution in Python
To solve this problem, we need to parse a string s representing a nested list, and convert it into a NestedInteger structure. The input string can represent either a single integer or a nested list of integers and other nested lists.
Approach:
- Handling Single Integers:
- If the input string does not start with
[, it must be a single integer. We can convert it directly into aNestedIntegerholding that integer.
- If the input string does not start with
- Parsing Nested Lists:
- If the input string starts with
[, it represents a nested list structure. - Use a stack to manage the nested structure as we encounter each
[and]:- When encountering
[, start a newNestedIntegerand push it to the stack. - When encountering
], pop the top element from the stack (the most recently completedNestedIntegerobject) and add it to theNestedIntegerbelow it (if it exists).
- When encountering
- Numbers are accumulated between commas
,or brackets[,].
- If the input string starts with
- Edge Cases:
- Empty lists (
[]). - Negative numbers and numbers with multiple digits.
- Direct integers without any nested lists.
- Empty lists (
Python
class Solution:
def deserialize(self, s: str) -> NestedInteger:
# If the string does not start with '[', it represents a single integer
if s[0] != '[':
# Convert the string to an integer and wrap it in a NestedInteger
return NestedInteger(int(s))
# Initialize a stack to keep track of NestedInteger objects
stack = []
# Initialize None for the current NestedInteger being built
current = None
# Variable to track the starting index of numbers in the string
num_start = None
# Iterate over each character in the string
for i, char in enumerate(s):
if char == '[':
# Start a new NestedInteger for a nested list
new_nested = NestedInteger()
if current:
# If there's an ongoing NestedInteger, add the new one to it
current.add(new_nested)
# Push the new NestedInteger onto the stack and set it as current
stack.append(new_nested)
current = new_nested
elif char == ']':
# If there was an ongoing number accumulation, complete it
if num_start is not None:
number = int(s[num_start:i])
current.add(NestedInteger(number))
num_start = None
# Pop the top NestedInteger since this nested list is complete
if stack:
completed = stack.pop()
if stack:
current = stack[-1] # Move back to the previous NestedInteger
else:
current = completed # The entire NestedInteger is complete
elif char == ',':
# If we encounter a comma and there was an ongoing number, add it
if num_start is not None:
number = int(s[num_start:i])
current.add(NestedInteger(number))
num_start = None
elif char == '-' or char.isdigit():
# Mark the start of a number
if num_start is None:
num_start = i
return currentExplanation of the Code:
- Single Integer Handling:
- If
sdoesn’t start with[, it’s a single integer. We wrap it in aNestedIntegerand return.
- If
- Stack for Nested Structure:
stackkeeps track of the hierarchy ofNestedIntegerobjects.- When we encounter
[, we start a newNestedInteger, add it to thecurrentNestedInteger (if one exists), and push it onto the stack. - When we encounter
], we pop from the stack, marking the end of the current nested structure.
- Handling Numbers:
- We track numbers using
num_start, the starting index of each number. - Once we reach
]or,, the accumulated number is parsed and added to thecurrentNestedInteger.
- We track numbers using
- Edge Case Handling:
- Empty lists are handled as
NestedInteger()objects with no additions. - Numbers are parsed correctly regardless of length and sign by marking their start with
num_start.
- Empty lists are handled as
Solution in C++
C++
class Solution {
public:
NestedInteger deserialize(string s) {
// If the string does not start with '[', it must be a single integer.
if (s[0] != '[') {
return NestedInteger(stoi(s)); // Return a NestedInteger with a single integer.
}
stack<NestedInteger> stk; // Stack to manage the nested structure.
int num = 0; // Variable to store number values.
bool negative = false; // Flag to handle negative numbers.
for (int i = 0; i < s.size(); ++i) {
char ch = s[i];
if (ch == '[') {
// Start of a new NestedInteger list; push a new empty NestedInteger onto the stack.
stk.push(NestedInteger());
} else if (ch == '-') {
// Negative sign; set the negative flag to true.
negative = true;
} else if (isdigit(ch)) {
// Parsing the number; convert from char to integer.
num = num * 10 + (ch - '0');
} else if (ch == ',' || ch == ']') {
// If we have a number to add, create a NestedInteger with it.
if (isdigit(s[i - 1])) { // Ensures we add the number only when it ends.
if (negative) num = -num; // Apply the negative flag if set.
stk.top().add(NestedInteger(num)); // Add number to the current top list.
num = 0; // Reset num for the next number.
negative = false; // Reset the negative flag.
}
if (ch == ']') {
// End of a list; pop the top NestedInteger from the stack.
NestedInteger ni = stk.top();
stk.pop();
if (!stk.empty()) {
// If the stack is not empty, add this nested integer to the next top list.
stk.top().add(ni);
} else {
// If the stack is empty, ni is the final result.
return ni;
}
}
}
}
// This line should not be reached for valid input.
return NestedInteger();
}
};Solution in Javascript
JavaScript
var deserialize = function(s) {
// If the string is a simple integer, return it as a NestedInteger with that integer
if (s[0] !== '[') {
let singleInteger = new NestedInteger();
singleInteger.setInteger(parseInt(s));
return singleInteger;
}
// Initialize a stack to keep track of nested lists
let stack = [];
let num = '';
let current = null;
// Loop through each character in the string
for (let i = 0; i < s.length; i++) {
let char = s[i];
if (char === '[') {
// Start a new NestedInteger list
let nestedList = new NestedInteger();
if (current !== null) {
// If there's a current list, add this new list as a nested element in it
current.add(nestedList);
}
// Push the current list to stack and set new list as current
stack.push(nestedList);
current = nestedList;
} else if (char === ']') {
// If a number was being accumulated, add it to the current list
if (num !== '') {
let integer = new NestedInteger();
integer.setInteger(parseInt(num));
current.add(integer);
num = '';
}
// Finish current list and pop to the previous level
if (stack.length > 0) {
current = stack.pop();
if (stack.length > 0) {
current = stack[stack.length - 1];
}
}
} else if (char === ',') {
// If a number was accumulated, add it to the current list
if (num !== '') {
let integer = new NestedInteger();
integer.setInteger(parseInt(num));
current.add(integer);
num = '';
}
} else {
// Accumulate digits (including '-' for negative numbers)
num += char;
}
}
// The root of the structure should be in the last item on the stack
return current;
};Solution in Java
Java
class Solution {
public NestedInteger deserialize(String s) {
// If the string represents a single integer, parse and return it directly
if (s.charAt(0) != '[') {
return new NestedInteger(Integer.parseInt(s));
}
// Stack to keep track of nested lists
Stack<NestedInteger> stack = new Stack<>();
// Temporary variable to hold current integer value
int num = 0;
// Boolean to manage negative numbers
boolean negative = false;
// The main `NestedInteger` to be returned as the result
NestedInteger current = null;
// Iterate through each character in the string
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '[') {
// Start a new NestedInteger for a new list
NestedInteger ni = new NestedInteger();
if (!stack.isEmpty()) {
// If there's an active list on the stack, add the new list as a nested element
stack.peek().add(ni);
}
// Push the new list onto the stack
stack.push(ni);
} else if (c == ']') {
// If an integer was being built, finalize and add it to the current list
if (Character.isDigit(s.charAt(i - 1)) || s.charAt(i - 1) == '-') {
NestedInteger ni = new NestedInteger(negative ? -num : num);
stack.peek().add(ni);
}
// Finished with the current list, so pop it from the stack
current = stack.pop();
// Reset num and negative flag for future use
num = 0;
negative = false;
} else if (c == ',') {
// If an integer was being accumulated, add it to the current list
if (Character.isDigit(s.charAt(i - 1)) || s.charAt(i - 1) == '-') {
NestedInteger ni = new NestedInteger(negative ? -num : num);
stack.peek().add(ni);
}
// Reset num and negative for next integer
num = 0;
negative = false;
} else if (c == '-') {
// If the character is a minus, mark the number as negative
negative = true;
} else if (Character.isDigit(c)) {
// Build the number by shifting left and adding the new digit
num = num * 10 + (c - '0');
}
}
// The last item in the stack is the completed NestedInteger structure
return current;
}
}