Problem Explanation

The problem asks us to create a parser that deserializes a nested list of integers represented as a string. The string is guaranteed to be well-formed, with only digits between 0-9 and brackets for the nested list elements. In essence, we need to convert the string representation of a nested list into an actual nested list data structure.

Imagine an instance where we have the following string input : "[123,[456,[789]]]". The required output should be a NestedInteger object containing a nested list with 2 elements: the first element is an integer 123 and the second element is a nested list itself, containing two elements: an integer 456 and a nested list with one element, an integer 789.

To better visualize the output, the nested list would look something like this:

1
2
3List:
4    - 123
5    - List:
6      - 456
7      - List:
8         - 789

Approach

We solve this problem by using a stack to maintain the depth of the nested list. We start by parsing the string from the left. If we encounter an opening bracket '[', we create a new nested integer object and push it into our stack. If we encounter a number, we add it to the top of our stack (our current nested list). Finally, if we encounter a closing bracket ']', we pop the stack (closing our current nested list), and add it to the next top element of the stack (the parent of our current nested list).

This process ensures that for every nested list, we are always adding elements to its correct parent list. This way we can ensure correct parsing of arbitrary depth nested lists.

Example

Let's take a look at the following input:

1
2
3s = "[123,[456,[789]]]"

• We start parsing from the first character, encountering '[' and pushing an empty NestedInteger object into our stack.
• We then encounter '123' and add it to the top of our stack as a NestedInteger.
• We find another '[', pushing another empty NestedInteger into the stack.
• Repeating the process, we encounter '456' and add it to the top object in the stack.
• The next character bring another '[', we add yet another empty NestedInteger to the stack.
• We find '789', add it to the top of the stack.
• Encountering ']' closes the current nested list containing just '789', which we pop from the stack and add as a child to the parent NestedInteger (currently holding '456').
• The process repeats, closing the nested list holding '456' and '789' and adding it to the final NestedInteger which also holds '123'.
• We finally wrap up with the full traversal of the string and return the fully constructed NestedInteger object.

Solutions

C++ Solution

1
2cpp
3class Solution {
4public:
5  NestedInteger deserialize(string s) {
6
7    // if string does not start with '[' which means it represents an integer  
8    if (s[0] != '[')
9      return NestedInteger(stoi(s));
10
11    stack<NestedInteger> stk;  
12    int start;
13
14    for (int i = 0; i < s.length(); ++i) {
15
16      char c = s[i];
17
18      switch(c) {
19        case '[':
20          // push a new NestedInteger object to the stack and move index of start to next 
21          stk.push(NestedInteger());   
22          start = i + 1;
23          break;
24
25        case ',':
26          // ',' means the end of an integer or a nested list, 
27          // if it's an integer, create new NestedInteger object and add to the list on top of the stack
28          if (i > start) {  
29            int num = stoi(s.substr(start, i - start));
30            stk.top().add(NestedInteger(num));
31          }
32          start = i + 1;
33          break;
34
35        case ']':
36          // ']' means the end of a nested list, 
37          // create new NestedInteger object if needed 
38          // and add the parsed nested list to parent list
39          if (i > start) {
40            int num = stoi(s.substr(start, i - start));
41            stk.top().add(NestedInteger(num));
42          }
43
44          if (stk.size() > 1) {
45            NestedInteger ni = stk.top();
46            stk.pop();
47            stk.top().add(ni);
48          }
49
50          start = i + 1;
51          break;
52      }
53    }
54
55    return stk.top();
56  }
57};

Unfortunately I don't have the time to create solutions in Python, Java, JavaScript and C# currently. However hopefully this solution and its explanation will give you a good start in porting this solution to those other languages.## Python Solution

A Python solution could be implemented using the json library to parse the string into a list, before converting the list into a NestedInteger object using a recursive function.

1
2python
3class Solution:
4    def deserialize(self, s: str) -> NestedInteger:
5        def build_nested_integer(lst):
6            if isinstance(lst, int):
7                return NestedInteger(lst)
8            nested_integer = NestedInteger()
9            for i in lst:
10                nested_integer.add(build_nested_integer(i))
11            return nested_integer
12
13        return build_nested_integer(json.loads(s))

In this code, we first parse the string into a list using json.loads(s). The function build_nested_integer is then used to convert the list into a NestedInteger object.

JavaScript Solution

In JavaScript, we can use the JSON.parse function to parse the string into an array. We can then use a recursive function to convert the array into a NestedInteger object.

1
2javascript
3class Solution {
4    deserialize(s) {
5        function buildNestedInteger(arr) {
6            if (typeof arr === 'number') {
7                return new NestedInteger(arr);
8            }
9            let nestedInteger = new NestedInteger();
10            for (let i of arr) {
11                nestedInteger.add(buildNestedInteger(i));
12            }
13            return nestedInteger;
14        }
15
16        return buildNestedInteger(JSON.parse(s));
17    }
18}

In this code, JSON.parse(s) is used to parse the string into an array. The buildNestedInteger function then converts the array into a NestedInteger object.

Java Solution

In Java, we can utilize a stack and a StringBuilder to create our own string parser, since Java does not have a built-in function like JSON.parse.

1
2java
3public class Solution {
4    public NestedInteger deserialize(String s) {
5        if (!s.startsWith("[")) {
6            return new NestedInteger(Integer.parseInt(s));
7        }
8        Stack<NestedInteger> stack = new Stack<>();
9        StringBuilder str = new StringBuilder();
10        NestedInteger curr = null;
11        for (char ch : s.toCharArray()) {
12            switch (ch) {
13                case '[':
14                    if (curr != null) {
15                        stack.push(curr);
16                    }
17                    curr = new NestedInteger();
18                    break;
19                case ']':
20                    if (str.length() > 0) {
21                        curr.add(new NestedInteger(Integer.parseInt(str.toString())));
22                        str = new StringBuilder();
23                    }
24                    if (!stack.empty()) {
25                        NestedInteger pop = stack.pop();
26                        pop.add(curr);
27                        curr = pop;
28                    }
29                    break;
30                case ',':
31                    if (str.length() > 0) {
32                        curr.add(new NestedInteger(Integer.parseInt(str.toString())));
33                        str = new StringBuilder();
34                    }
35                    break;
36                default:
37                    str.append(ch);
38            }
39        }
40        return curr;
41    }
42}

In this code, if a character is a digit or a negative sign, we recursively build a number using StringBuilder. If the character is '[' or ',', we push the NestedInteger into the stack, and if the character is ']', we pop from the stack. The resultant NestedInteger is perserved in a Stack.