Watch 10 video solutions for Mini Parser, a medium level problem involving String, Stack, Depth-First Search. This walkthrough by NeetCode has 427,689 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |