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!