FAANG · LeetCode #385

Mini Parser — three-stage drill

1The ProblemMedium

Mini Parser

Deserialize a string like "[123,[456,789]]" into its nested-integer structure.

Examples

"324"→ 324"[123,[456,789]]"→ [123, [456, 789]]

constraintThe string is a valid nested-list encoding; integers may be negative.

2The PatternTIME O(n) · SPACE O(d)

Recursive Descent

Parse a structured string top-down: each grammar rule is a function, and one lookahead character tells you which to call next. Nesting is handled by recursion, and — unlike backtracking — a choice is never undone, because the next character is always enough to decide.

Problems using this pattern

3The SolutionRESULT → [12, [34]]

Step through it

'[' → start a list, recurse into parse_list

Step 1 / 7

Python▎lookahead char picks the branch · '[' recurses · ']' returns · cursor only moves forward

1def deserialize(s):
2    if s[0] != "[":
3        return NestedInteger(int(s))   # a bare integer
4 
5    i = 0
6 
7    def parse_list():
8        nonlocal i
9        ni = NestedInteger()
10        i += 1                          # consume '['
11        while s[i] != "]":
12            if s[i] == "[":
13                ni.add(parse_list())    # nested list -> recurse
14            elif s[i] == ",":
15                i += 1                  # skip the separator
16            else:
17                start = i               # read an integer
18                if s[i] == "-":
19                    i += 1
20                while s[i].isdigit():
21                    i += 1
22                ni.add(NestedInteger(int(s[start:i])))
23        i += 1                          # consume ']'
24        return ni
25 
26    return parse_list()

why it worksWalk the string with a single cursor. parse_list() consumes the opening '[', then loops on the lookahead character: '[' means a nested list (recurse), a digit (or '-') means read an integer, ',' is a separator to skip, and ']' closes the current list and returns. The cursor only ever moves forward — the next character always decides the branch, so there is no backtracking. Recursion depth tracks the nesting depth: O(n) time, O(d) stack.

Mini Parser — three-stage drill

Mini Parser

Recursive Descent

Step through it

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Heap / Top-K

Backtracking

Recursive Descent