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.
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 789
Constraints:
1 <= s.length <= 5 * 104s consists of digits, square brackets "[]", negative sign '-', and commas ','.s is the serialization of valid NestedInteger.[-106, 106].Problem Overview: You receive a string that represents a nested list of integers such as [123,[456,[789]]]. The goal is to deserialize this string into a NestedInteger structure where each element is either a single integer or a list of nested integers.
Approach 1: Stack-Based Parsing (O(n) time, O(n) space)
This approach processes the string character by character while maintaining a stack of partially constructed NestedInteger objects. Whenever you encounter an opening bracket '[', create a new list and push the current object onto the stack. When digits (or a negative sign) appear, parse the full integer value and add it to the current list. On encountering a closing bracket ']', the current nested list is complete, so pop the parent from the stack and attach the finished list to it.
The key insight is that nested lists follow a clear hierarchical structure, which stacks model naturally. Each '[' represents a new context and each ']' ends it. Because each character in the string is processed exactly once, the runtime is O(n), where n is the string length. The stack can grow to the depth of nesting, giving O(n) space in the worst case. This technique heavily relies on string parsing and stack operations similar to problems in string and stack processing.
Approach 2: Recursive Deserialization (O(n) time, O(n) space)
Recursive parsing mirrors the nested structure of the input directly. When the parser sees '[', it recursively constructs a list until the corresponding closing bracket appears. If the current character starts a number, parse the integer and return a single NestedInteger containing that value.
The recursion naturally handles nested lists: each recursive call processes one sublist and returns it to its parent. A shared index pointer moves through the string so every character is parsed once. This results in O(n) time complexity and up to O(n) space due to recursion depth and the constructed data structure.
This solution closely resembles recursive tree or graph parsing patterns. Conceptually, the string is treated like a preorder traversal of a nested structure, making the technique similar to problems solved using depth-first search.
Recommended for interviews: The stack-based parser is typically preferred because it demonstrates explicit control over parsing state and avoids recursion limits. Many interviewers expect this approach for serialization/deserialization problems. Still, explaining the recursive method first can show strong understanding of the nested structure before implementing the iterative stack solution.
This approach uses a stack to manage NestedInteger objects as we traverse the string. When encountering '[', a new NestedInteger object is created and pushed onto the stack. When encountering ']', the top object is popped and added to the NestedInteger on the top of the stack (if any). Numbers are parsed and added as individual NestedIntegers.
The solution in C involves writing or assuming existing implementations for NestedInteger operations, then using a stack to process the string character by character.
Time Complexity: O(n), where n is the length of the string s.
Space Complexity: O(n), for the stack and dynamic NestedInteger objects.
This approach leverages recursion to simplify handling nested structures. By using a helper function with an index parameter, the parsing function can call itself to deserialize nested lists efficiently.
The C solution for this approach would involve crafting a recursive function that handles the index traversal through the string, invoking itself for nested brackets.
Time Complexity: O(n), where n is the length of s, though work specific to C may yield additional nuances for dynamic operations.
Space Complexity: O(n), due to recursion depth and dynamic NestedInteger allocations.
We first judge whether the string s is empty or an empty list. If so, simply return an empty NestedInteger. If s is an integer, we simply return a NestedInteger containing this integer. Otherwise, we traverse the string s from left to right. If the current depth is 0 and we encounter a comma or the end of the string s, we take a substring and recursively call the function to parse the substring and add the return value to the list. Otherwise, if the current encounter is a left parenthesis, we increase the depth by 1 and continue to traverse. If we encounter a right parenthesis, we decrease the depth by 1 and continue to traverse.
After the traversal is over, return the answer.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string s.
Python
Java
C++
Go
TypeScript
We can use a stack to simulate the recursive process.
We first judge whether the string s is an integer. If so, we simply return a NestedInteger containing this integer. Otherwise, we traverse the string s from left to right. For the character c currently traversed:
c is a negative sign, we set the negative sign to true;c is a number, we add the number to the current number x, where the initial value of x is 0;c is a left parenthesis, we push a new NestedInteger onto the stack;c is a right parenthesis or comma, we judge whether the previous character of the current character is a number. If so, we add the current number x to the top NestedInteger of the stack according to the negative sign, and then reset the negative sign to false and the current number x to 0. If c is a right parenthesis and the size of the current stack is greater than 1, we pop the top NestedInteger of the stack and add it to the top NestedInteger of the stack.After the traversal is over, return the top NestedInteger of the stack.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string s.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Stack-Based Parsing | Time Complexity: O(n), where n is the length of the string s. |
| Recursive Deserialization | Time Complexity: O(n), where n is the length of s, though work specific to C may yield additional nuances for dynamic operations. |
| Recursion | — |
| Stack | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Parsing | O(n) | O(n) | Best general solution. Explicit control over nested structure and commonly expected in interviews. |
| Recursive Deserialization | O(n) | O(n) | Clean and intuitive when recursion is allowed and nesting depth is manageable. |
Leetcode Question 385 "Mini Parser" in Java • Ghumman Tech • 914 views views
Watch 7 more video solutions →Practice Mini Parser with our built-in code editor and test cases.
Practice on FleetCode