Last updated on February 9th, 2025 at 05:50 am

Here, we see the Mini Parser LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Stack, String

Companies

Airbnb

Level of Question

Medium

Mini Parser LeetCode Solution

1. Problem Statement

Given a string s represents the serialization of a nested list, implement a parser to deserialize it and return the deserialized NestedInteger.

Each element is either an integer or a list whose elements may also be integers or other lists.

Example 1:
Input: s = “324”
Output: 324
Explanation: You should return a NestedInteger object which contains a single integer 324.

Example 2:
Input: s = “[123,[456,[789]]]”
Output: [123,[456,[789]]]
Explanation: Return a NestedInteger object containing a nested list with 2 elements: 1. An integer containing value 123. 2. A nested list containing two elements: i. An integer containing value 456. ii. A nested list with one element: a. An integer containing value 789

2. Coding Pattern Used in Solution

The provided code implements a Recursive Parsing pattern. The code recursively parses a nested string representation of integers and lists (e.g., "[123,[456,[789]]]") into a NestedInteger object.

3. Code Implementation in Different Languages

3.1 Mini Parser C++

class Solution {
public:
    NestedInteger deserialize(string s) {
        istringstream in(s);
        return deserialize(in);
    }
private:
    NestedInteger deserialize(istringstream &in) {
        int number;
        if (in >> number)
            return NestedInteger(number);
        in.clear();
        in.get();
        NestedInteger list;
        while (in.peek() != ']') {
            list.add(deserialize(in));
            if (in.peek() == ',')
                in.get();
        }
        in.get();
        return list;
    }
};

3.2 Mini Parser Java

class Solution {
    public NestedInteger deserialize(String s) {
        if(s.length()==0 || s.equals("[]")) return new NestedInteger();
        NestedInteger ni = new NestedInteger();
        char[] chars = s.toCharArray();
        if(chars[0]=='[') {
            int elementStart = 1;
            while(elementStart<chars.length) {
                int elementEnd = searchForElementEnd(chars,elementStart);
                String nextListElement = new String(chars,elementStart,elementEnd-elementStart);
                ni.add(deserialize(nextListElement));
                elementStart=elementEnd+1;
            }
        } else ni.setInteger(new Integer(new String(chars)));
        return ni;
    }

    private int searchForElementEnd(char[] chars, int elementStart) {
        int countBrackets = 0;
        int i=elementStart;
        if(chars[i++]=='[') countBrackets++;
        while(i<chars.length) {
            char nextChar = chars[i];
            if(nextChar==']') {
                countBrackets--;
                if(countBrackets<=0) {
                    if(countBrackets==0) i++;
                    break;
                }
            }
            else if(nextChar=='[') countBrackets++;
            else if(nextChar==',' && countBrackets==0) {
                break;
            }
            i++;
        }
        return i;
    }
}

3.3 Mini Parser JavaScript

var deserialize = function(s) {
    if(!s) return null
    s = JSON.parse(s)
    let n = new NestedInteger()
    function fn(nt, s) {
        if(Array.isArray(s)) {
            let a = new NestedInteger()
            for(let item of s) {
                let ret = fn(a, item)
                a.add(ret)
            }
            return a
        }
        return new NestedInteger(s)
    }
    let ret = fn(n, s)
    return ret
};

3.4 Mini Parser Python

class Solution(object):
    def deserialize(self, s):
        def nestedInteger(x):
            if isinstance(x, int):
                return NestedInteger(x)
            lst = NestedInteger()
            for y in x:
                lst.add(nestedInteger(y))
            return lst
        return nestedInteger(eval(s))

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(n + d)
Java	O(n)	O(n + d)
JavaScript	O(n)	O(n + d)
Python	O(n)	O(n + d)

where,
n is the length of the string.
d is the maximum depth of the nested structure.