Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

385. Mini Parser - Leetcode Solution

Code Implementation

# This solution assumes NestedInteger class is provided by Leetcode.
class Solution:
    def deserialize(self, s: str) -> 'NestedInteger':
        if not s:
            return None
        if s[0] != '[':
            return NestedInteger(int(s))
        stack = []
        num = ''
        for i, ch in enumerate(s):
            if ch == '[':
                stack.append(NestedInteger())
            elif ch == ']':
                if num:
                    stack[-1].add(NestedInteger(int(num)))
                    num = ''
                if len(stack) > 1:
                    ni = stack.pop()
                    stack[-1].add(ni)
            elif ch == ',':
                if num:
                    stack[-1].add(NestedInteger(int(num)))
                    num = ''
            else:
                num += ch
        return stack[0]
      
// This solution assumes NestedInteger class is provided by Leetcode.
class Solution {
public:
    NestedInteger deserialize(string s) {
        if (s.empty()) return NestedInteger();
        if (s[0] != '[') return NestedInteger(stoi(s));
        stack<NestedInteger> st;
        int num = 0, sign = 1;
        bool hasNum = false;
        for (int i = 0; i < s.size(); ++i) {
            char c = s[i];
            if (c == '[') {
                st.push(NestedInteger());
            } else if (c == '-' || isdigit(c)) {
                sign = (c == '-') ? -1 : 1;
                int j = i;
                if (c == '-') ++j;
                num = 0;
                while (j < s.size() && isdigit(s[j])) {
                    num = num * 10 + (s[j] - '0');
                    ++j;
                }
                num *= sign;
                st.top().add(NestedInteger(num));
                i = j - 1;
            } else if (c == ']') {
                if (st.size() > 1) {
                    NestedInteger ni = st.top(); st.pop();
                    st.top().add(ni);
                }
            }
        }
        return st.top();
    }
};
      
// This solution assumes NestedInteger class is provided by Leetcode.
public class Solution {
    public NestedInteger deserialize(String s) {
        if (s.isEmpty()) return null;
        if (s.charAt(0) != '[') return new NestedInteger(Integer.parseInt(s));
        Stack<NestedInteger> stack = new Stack<>();
        int num = 0, sign = 1;
        boolean hasNum = false;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (c == '[') {
                stack.push(new NestedInteger());
            } else if (c == '-' || Character.isDigit(c)) {
                sign = (c == '-') ? -1 : 1;
                int j = i;
                if (c == '-') ++j;
                num = 0;
                while (j < s.length() && Character.isDigit(s.charAt(j))) {
                    num = num * 10 + (s.charAt(j) - '0');
                    ++j;
                }
                num *= sign;
                stack.peek().add(new NestedInteger(num));
                i = j - 1;
            } else if (c == ']') {
                if (stack.size() > 1) {
                    NestedInteger ni = stack.pop();
                    stack.peek().add(ni);
                }
            }
        }
        return stack.peek();
    }
}
      
// This solution assumes NestedInteger class is provided by Leetcode.
var deserialize = function(s) {
    if (s[0] !== '[') return new NestedInteger(parseInt(s));
    let stack = [];
    let num = '';
    for (let i = 0; i < s.length; ++i) {
        let ch = s[i];
        if (ch === '[') {
            stack.push(new NestedInteger());
        } else if (ch === ']') {
            if (num.length) {
                stack[stack.length - 1].add(new NestedInteger(parseInt(num)));
                num = '';
            }
            if (stack.length > 1) {
                let ni = stack.pop();
                stack[stack.length - 1].add(ni);
            }
        } else if (ch === ',') {
            if (num.length) {
                stack[stack.length - 1].add(new NestedInteger(parseInt(num)));
                num = '';
            }
        } else {
            num += ch;
        }
    }
    return stack[0];
};

Problem Description

The Mini Parser problem asks you to implement a parser for a string that represents nested lists of integers. The string input s can represent:
  • A single integer (e.g., "123")
  • A nested list of integers (e.g., "[123,[456,[789]]]")
Your task is to convert this string into a data structure (provided by Leetcode as NestedInteger) that can represent either a single integer or a nested list of integers.

Key Constraints:
  • Input string s is always valid and well-formed.
  • There is only one valid way to interpret the string.
  • You must not reuse parsed elements; create new NestedInteger objects as needed.
  • The NestedInteger interface is provided; you only need to implement the parsing logic.

Thought Process

At first glance, the problem looks like parsing mathematical expressions or processing JSON. A brute-force approach would be to recursively split the string at every comma and bracket, but that quickly gets complicated with nested lists.

Instead, it's helpful to:
  • Recognize that nested structures are best handled with a stack or recursion.
  • Notice that every '[' signals the start of a new nested list, and every ']' signals the end of one.
  • Numbers (including negative numbers) can appear anywhere, and must be collected character by character.
  • We need to distinguish between parsing single integers and lists.
The challenge is to correctly build the NestedInteger structure as we parse, keeping track of context as we enter and exit nested lists.

Solution Approach

The optimal solution uses a stack to manage nested contexts as we parse the string from left to right.
  • Step 1: If the string does not start with '[', it is just a single integer. Return a NestedInteger holding that value.
  • Step 2: Otherwise, initialize an empty stack. Each time we see '[', push a new empty NestedInteger (representing a list) onto the stack.
  • Step 3: As we read digits (and optional '-'), accumulate them into a number string.
  • Step 4: When we reach a ',' or ']', if we have accumulated digits, convert them to an integer, wrap them in a NestedInteger, and add to the current top list.
  • Step 5: When we reach ']', pop the top NestedInteger from the stack, and add it to the next top (its parent list), unless it's the outermost list.
  • Step 6: At the end, the stack contains the fully constructed NestedInteger structure at its bottom.
Design Choices:
  • Using a stack makes it easy to manage nesting, since each '[' and ']' naturally maps to push and pop.
  • We only parse numbers when a separator (',' or ']') is encountered, which ensures we handle multi-digit and negative numbers correctly.

Example Walkthrough

Let's walk through the input "[123,[456,[789]]]":
  • Step 1: See '[', push new list onto stack.
  • Step 2: Read '1', '2', '3' → accumulate num = "123".
  • Step 3: See ',', convert "123" to integer, add NestedInteger(123) to top list.
  • Step 4: See '[', push new list onto stack.
  • Step 5: Read '4', '5', '6' → accumulate num = "456".
  • Step 6: See ',', convert "456" to integer, add NestedInteger(456) to top list.
  • Step 7: See '[', push new list onto stack.
  • Step 8: Read '7', '8', '9' → accumulate num = "789".
  • Step 9: See ']', convert "789" to integer, add NestedInteger(789) to top list. Pop this list, add it to its parent.
  • Step 10: See ']', pop current list, add to parent.
  • Step 11: See ']', parsing is done.
The final structure is a NestedInteger list containing 123 and another list which contains 456 and another list containing 789.

Time and Space Complexity

  • Brute-force approach: Recursively splitting at every comma and bracket leads to O(n^2) time in the worst case due to repeated string operations.
  • Optimized (stack-based) approach: Each character is processed once, so time complexity is O(n), where n is the length of the input string.
  • Space complexity is also O(n), since in the worst case (deeply nested), the stack and the constructed data structure together may use space proportional to the input size.

Summary

The Mini Parser problem is a classic example of parsing nested structures. By using a stack to track nested contexts and only constructing numbers when a separator is reached, we elegantly and efficiently build the required NestedInteger structure. This approach ensures we handle all valid inputs, including single integers and arbitrarily nested lists, with optimal O(n) time and space complexity.