LeetCode 385: Mini Parser Solution in Python – A Step-by-Step Guide
Imagine you’re given a string like "[123,[456,[789]]]"—a nested list of integers—and you need to parse it into an actual nested structure, handling numbers and brackets with precision. That’s the challenge of LeetCode 385: Mini Parser, a medium-level problem that’s all about string parsing and nested data representation. Using Python, we’ll explore two solutions: the Best Solution—a stack-based approach for O(n) efficiency—and an Alternative Solution—recursion at O(n). With examples, clear code breakdowns, and a friendly vibe, this guide will help you parse that string. Let’s dive into the brackets!
What Is LeetCode 385: Mini Parser?
LeetCode 385: Mini Parser provides a string representing a nested list of integers (e.g., "[123,[456,789]]"), and your task is to implement a deserialize
method that converts it into a NestedInteger
object—a custom class supporting nested lists and single integers. The problem tests your ability to parse structured data efficiently!
Problem Statement
- Class: NestedInteger
- Methods: isInteger(), getInteger(), setInteger(), add(), getList().
- Method:
- deserialize(s): Convert string s to a NestedInteger object.
- Input:
- s: String representing a nested list of integers.
- Output: NestedInteger - Parsed nested structure.
- Rules:
- String contains integers, commas, and brackets.
- Integers are non-negative, no leading zeros.
Constraints
- 1 <= s.length <= 5 * 10⁴
- s contains digits (0-9), '[', ']', and ','.
- Input is a valid nested list string.
- Integers: 0 to 10⁹.
Examples
- Input: s = "[123,[456,[789]]]"
- Output: [123,[456,[789]]]
- NestedInteger: [123, [456, [789]]].
- Input: s = "324"
- Output: 324
- NestedInteger: 324 (single integer).
- Input: s = "[123,456]"
- Output: [123,456]
- NestedInteger: [123, 456].
These show the nested parsing—let’s solve it!
Understanding the Problem: Parsing Nested Integers
To tackle LeetCode 385 in Python, we need to: 1. Parse a string into a NestedInteger object. 2. Handle nested brackets, commas, and integers. 3. Build the structure efficiently.
A naive approach might scan repeatedly, but we can do better. We’ll use:
- Best Solution: Stack—O(n) time, O(n) space—fast and iterative.
- Alternative Solution: Recursion—O(n) time, O(n) space—intuitive but recursive.
Let’s parse with the best solution!
Best Solution: Stack
Why This Is the Best Solution
The stack-based approach runs in O(n) time (n is string length) with O(n) space by processing the string left-to-right in one pass, using a stack to manage nested levels. It’s the most efficient—handling all cases iteratively without recursion’s overhead, making it clear and fast!
How It Works
Think of it like stacking boxes:
- Stack: Holds NestedInteger objects at each nesting level.
- Process:
- '[': Push new NestedInteger list.
- Digit: Build number, add as NestedInteger when complete.
- ',': Add completed number to current list.
- ']': Pop list, add to parent list (or finish if top-level).
- Result: Top stack element (or single integer).
It’s like assembling nested boxes as you go!
Step-by-Step Example
For s = "[123,[456,[789]]]"
:
- Init: Stack = [], num = None.
- '[': Push new NestedInteger, Stack = [NI()].
- '1': num = 1.
- '2': num = 12.
- '3': num = 123.
- '[': Add NI(123) to top, push new NI, Stack = [NI([123]), NI()].
- '4': num = 4.
- '5': num = 45.
- '6': num = 456.
- '[': Add NI(456) to top, push new NI, Stack = [NI([123]), NI([456]), NI()].
- '7': num = 7.
- '8': num = 78.
- '9': num = 789.
- ']': Add NI(789) to top, pop to parent, Stack = [NI([123]), NI([456,[789]])].
- ']': Pop to parent, Stack = [NI([123,[456,[789]]])].
- ']': Pop final, return NI([123,[456,[789]]]).
For s = "324"
:
- '3': num = 3.
- '2': num = 32.
- '4': num = 324.
- End: Return NI(324).
Code with Explanation
Here’s the Python code using a stack:
class Solution:
def deserialize(self, s: str) -> 'NestedInteger':
if not s:
return NestedInteger()
# If single integer (no brackets)
if s[0] != '[':
return NestedInteger(int(s))
stack = []
num = None
for char in s:
if char == '[':
# Start new nested list
stack.append(NestedInteger())
elif char.isdigit():
# Build number
num = num * 10 + int(char) if num is not None else int(char)
elif char == ',' and num is not None:
# Add completed number to current list
stack[-1].add(NestedInteger(num))
num = None
elif char == ']':
# Finish current list
if num is not None:
stack[-1].add(NestedInteger(num))
num = None
if len(stack) > 1:
top = stack.pop()
stack[-1].add(top)
# Handle top-level number if present
if num is not None:
return NestedInteger(num)
return stack[0]
Explanation
- Lines 3-7: Handle empty string or single integer case—O(n) for conversion.
- Lines 9-10: stack: For nested levels, num: Build current number.
- Lines 12-27: Parse string:
- '[': Push new NestedInteger—O(1).
- Digit: Build num (e.g., 12 → 123)—O(1).
- ',': Add completed num to top list, reset num—O(1).
- ']': Add num if present, pop and add to parent if not top-level—O(1).
- Lines 29-32: Return single num or top stack element—O(1).
- Time: O(n)—single pass through string.
- Space: O(n)—stack size up to nesting depth.
This is like a bracket assembler—swift and steady!
Alternative Solution: Recursion
Why an Alternative Approach?
The recursive solution also runs in O(n) time with O(n) space by parsing the string top-down, using recursion to handle nested brackets. It’s more intuitive—great for understanding the hierarchical structure, though it uses stack space and is less iterative than the best solution!
How It Works
- Recurse: Parse string, return NestedInteger for each segment.
- Base: Single integer or empty list.
- Process: Handle brackets, numbers, and commas recursively.
- Result: Build nested structure.
Step-by-Step Example
For s = "[123,[456]]"
:
- Parse '[123,[456]]':
- '[' → New NI list.
- "123": NI(123).
- ',': Add NI(123) to list.
- "[456]": Recurse → NI([456]).
- ']': Finish list, return NI([123,[456]]).
- "456": NI(456).
- Result: NI([123,[456]]).
For s = "324"
:
- Parse: NI(324).
Code with Explanation
class Solution:
def deserialize(self, s: str) -> 'NestedInteger':
def parse(s, i):
# Base case: single integer
if i >= len(s) or s[i] == ',' or s[i] == ']':
return None, i
# Handle integer
if s[i].isdigit():
num = 0
while i < len(s) and s[i].isdigit():
num = num * 10 + int(s[i])
i += 1
return NestedInteger(num), i
# Handle nested list
if s[i] == '[':
ni = NestedInteger()
i += 1
while i < len(s) and s[i] != ']':
child, i = parse(s, i)
if child:
ni.add(child)
if i < len(s) and s[i] == ',':
i += 1
return ni, i + 1
return None, i
# Start parsing from index 0
result, _ = parse(s, 0)
return result
Explanation
- Lines 3-22: parse(s, i):
- Base: Return None if at end, comma, or bracket—O(1).
- Digit: Build number, return NI(num)—O(k) for digits.
- '[': Create new NI, recurse for children until ']', handle commas—O(n) total.
- Line 25: Start parsing at index 0—O(n).
- Time: O(n)—single pass, recursive.
- Space: O(n)—recursion stack up to nesting depth.
It’s a recursive parser—clear but stacked!
Comparing the Two Solutions
- Stack (Best):
- Time: O(n)—iterative pass.
- Space: O(n)—stack.
- Pros: Fast, no recursion overhead.
- Cons: Slightly more manual.
- Recursion (Alternative):
- Time: O(n)—recursive pass.
- Space: O(n)—stack.
- Pros: Intuitive nesting.
- Cons: Recursion depth risk.
Stack wins for efficiency and iteration!
Additional Examples and Edge Cases
- "": Stack handles empty, recursion too.
- "[1]": Both return NI([1]).
- Deep nesting: Stack scales linearly.
Both work, stack is cleaner.
Complexity Breakdown
- Stack:
- Time: O(n).
- Space: O(n).
- Recursion:
- Time: O(n).
- Space: O(n).
Stack excels for iterative simplicity.
Key Takeaways
- Stack: Parse iteratively—fast and lean!
- Recursion: Parse hierarchically—clear but stacked!
- Parsing: Structure drives solutions.
- Python Tip: Loops rock—see [Python Basics](/python/basics).
Final Thoughts: Parse That List
LeetCode 385: Mini Parser in Python is a parsing challenge. Stack-based is the efficiency champ, while recursion offers intuitive nesting. Want more? Try LeetCode 394: Decode String or LeetCode 341: Flatten Nested List Iterator. Ready to parse? Visit Solve LeetCode 385 on LeetCode and build that structure today!