Mini Parser

Med

#0372Time: O(N), where N is the length of the input string. Each character of the string is examined a constant number of times.Space: O(D), where D is the maximum nesting depth of the list. In the worst-case scenario (e.g., `"[[[[...]]]]"`), the depth D can be proportional to the length of the string N, making the space complexity O(N). This space is used by the recursion call stack.1 company

Algorithms

Depth-First Search

Data structures

String Stack

Companies

Airbnb

Prompt

[Fetch error]

Approaches

2 approaches with complexity analysis and trade-offs.

This approach leverages recursion, which is a natural fit for parsing nested or tree-like data structures. The function calls itself to handle nested lists, effectively performing a depth-first traversal of the nested structure represented by the string.

Algorithm

The core idea is to use a recursive helper function that parses a portion of the string and advances a global or passed-by-reference index.
The main deserialize function checks if the string represents a single number (i.e., does not start with [). If so, it parses it and returns.
Otherwise, it calls a recursive helper function to parse the list.
The recursive helper function, say parse(s, index):
- If the character at the current index is '[', it knows it's parsing a list. It creates a new NestedInteger list.
- It then enters a loop, continuing as long as the character at the index is not ']'. Inside the loop, it recursively calls parse to get the next element (which could be a number or another list) and adds it to the current list.
- It handles commas by simply advancing the index.
- Once it hits ']', it advances the index past it and returns the created list.
- If the character at the current index is a digit or a '-', it knows it's parsing a number. It reads all consecutive digits to form the number string, parses it to an integer, creates a NestedInteger with this value, and returns it.

Walkthrough

We can design a recursive function that is responsible for parsing one NestedInteger element from the string, starting at a given index. Since we need to keep track of our progress through the string across recursive calls, we can pass an index by reference (e.g., using a single-element array int[]) or use a class member for the index.

The base case for the recursion is a number. If the substring to be parsed does not start with '[', we parse it as an integer.

The recursive step handles lists. If the substring starts with '[', we create a new NestedInteger to act as a list. We then iterate, recursively calling the function to parse each element within the brackets until we encounter the closing ']'. Commas are used as delimiters to separate elements.

1/**2 * // This is the interface that allows for creating nested lists.3 * // You should not implement it, or speculate about its implementation4 * public interface NestedInteger {5 *     // Constructor initializes an empty nested list.6 *     public NestedInteger();7 *8 *     // Constructor initializes a single integer.9 *     public NestedInteger(int value);10 *11 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.12 *     public boolean isInteger();13 *14 *     // @return the single integer that this NestedInteger holds, if it holds a single integer15 *     // Return null if this NestedInteger holds a nested list16 *     public Integer getInteger();17 *18 *     // Set this NestedInteger to hold a single integer.19 *     public void setInteger(int value);20 *21 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.22 *     public void add(NestedInteger ni);23 *24 *     // @return the nested list that this NestedInteger holds, if it holds a nested list25 *     // Return null if this NestedInteger holds a single integer26 *     public List<NestedInteger> getList();27 * }28 */29class Solution {30    private int index = 0;31 32    public NestedInteger deserialize(String s) {33        // If the string doesn't start with '[', it's a single integer.34        // This check is implicitly handled by the logic below.35        return parse(s);36    }37 38    private NestedInteger parse(String s) {39        if (s.charAt(index) == '[') {40            index++; // Skip '['41            NestedInteger ni = new NestedInteger();42            while (s.charAt(index) != ']') {43                ni.add(parse(s));44                if (s.charAt(index) == ',') {45                    index++; // Skip ','46                }47            }48            index++; // Skip ']'49            return ni;50        } else {51            // It's a number52            int start = index;53            while (index < s.length() && (Character.isDigit(s.charAt(index)) || s.charAt(index) == '-')) {54                index++;55            }56            int num = Integer.parseInt(s.substring(start, index));57            return new NestedInteger(num);58        }59    }60}

Complexity

Time

O(N), where N is the length of the input string. Each character of the string is examined a constant number of times.

Space

O(D), where D is the maximum nesting depth of the list. In the worst-case scenario (e.g., `"[[[[...]]]]"`), the depth D can be proportional to the length of the string N, making the space complexity O(N). This space is used by the recursion call stack.

Trade-offs

Pros

The code is often more concise and easier to understand because it directly mirrors the nested definition of the data structure.
It's a very natural way to think about problems involving recursion and nested hierarchies.

Cons

For very deeply nested input strings, this approach can lead to a StackOverflowError due to deep recursion.
The overhead of function calls might make it slightly less performant than an iterative solution.

Solutions

Solution

1/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * public interface NestedInteger { * // Constructor initializes an empty nested list. * public NestedInteger(); * * // Constructor initializes a single integer. * public NestedInteger(int value); * * // @return true if this NestedInteger holds a single integer, rather than a nested list. * public boolean isInteger(); * * // @return the single integer that this NestedInteger holds, if it holds a single integer * // Return null if this NestedInteger holds a nested list * public Integer getInteger(); * * // Set this NestedInteger to hold a single integer. * public void setInteger(int value); * * // Set this NestedInteger to hold a nested list and adds a nested integer to it. * public void add(NestedInteger ni); * * // @return the nested list that this NestedInteger holds, if it holds a nested list * // Return empty list if this NestedInteger holds a single integer * public List<NestedInteger> getList(); * } */ class Solution { public NestedInteger deserialize ( String s ) { if ( s . charAt ( 0 ) != '[' ) { return new NestedInteger ( Integer . parseInt ( s )); } Deque < NestedInteger > stk = new ArrayDeque <>(); int x = 0 ; boolean neg = false ; for ( int i = 0 ; i < s . length (); ++ i ) { char c = s . charAt ( i ); if ( c == '-' ) { neg = true ; } else if ( Character . isDigit ( c )) { x = x * 10 + c - '0' ; } else if ( c == '[' ) { stk . push ( new NestedInteger ()); } else if ( c == ',' || c == ']' ) { if ( Character . isDigit ( s . charAt ( i - 1 ))) { if ( neg ) { x = - x ; } stk . peek (). add ( new NestedInteger ( x )); } x = 0 ; neg = false ; if ( c == ']' && stk . size () > 1 ) { NestedInteger t = stk . pop (); stk . peek (). add ( t ); } } } return stk . peek (); } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem