Mini Parser Problem

Problem

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.

Examples

Example 1:

1
2
3


Input: s = "324"
Output: 324
Explanation: You should return a NestedInteger object which contains a single integer 324.

Example 2:

1
2
3
4
5
6
7
8


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

Solution

Method 1 - Using Stack

Here is the approach:

Initialization: Use a stack to store intermediate NestedInteger objects and a variable to keep track of the current number being processed.
Traversal: Traverse the string character by character.
- When encountering '[', create a new NestedInteger and push it onto the stack.
- When encountering digits (or '-' for negative numbers), build the number.
- When encountering ',' or ']', finalize the current number and append it to the last NestedInteger on the stack.
- Particularly, when encountering ']', pop the top NestedInteger from the stack and append it to the next top if the stack is not empty.
Edge Cases: Return the single NestedInteger remaining in the stack at the end of traversal.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


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<>();
        NestedInteger curr = null;
        int l = 0; // pointer to the start of the number
        
        for (int r = 0; r < s.length(); r++) {
            char ch = s.charAt(r);
            
            if (ch == '[') {
                if (curr != null) {
                    stack.push(curr);
                }
                curr = new NestedInteger();
                l = r + 1;
            } else if (ch == ']') {
                String num = s.substring(l, r);
                if (!num.isEmpty()) {
                    curr.add(new NestedInteger(Integer.parseInt(num)));
                }
                if (!stack.isEmpty()) {
                    NestedInteger top = stack.pop();
                    top.add(curr);
                    curr = top;
                }
                l = r + 1;
            } else if (ch == ',') {
                if (s.charAt(r - 1) != ']') {
                    String num = s.substring(l, r);
                    curr.add(new NestedInteger(Integer.parseInt(num)));
                }
                l = r + 1;
            }
        }
        
        return curr;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


class NestedInteger:
    def __init__(self, value: Union[int, None] = None):
        self.value = value
        self.list = [] if value is None else None

    def isInteger(self) -> bool:
        return self.value is not None

    def add(self, ni: 'NestedInteger') -> None:
        if self.list is not None:
            self.list.append(ni)

    def setInteger(self, value: int) -> None:
        self.value = value

    def getInteger(self) -> Union[int, None]:
        return self.value

    def getList(self) -> Union[None, list]:
        return self.list

class Solution:
    def deserialize(self, s: str) -> NestedInteger:
        if not s:
            return NestedInteger()
        if s[0] != '[':
            return NestedInteger(int(s))

        stack, l = [], 0
        curr = None
        
        for r in range(len(s)):
            char = s[r]
            
            if char == '[':
                if curr is not None:
                    stack.append(curr)
                curr = NestedInteger()
                l = r + 1
            elif char == ']':
                num = s[l:r]
                if num:
                    curr.add(NestedInteger(int(num)))
                if stack:
                    top = stack.pop()
                    top.add(curr)
                    curr = top
                l = r + 1
            elif char == ',':
                if s[r - 1] != ']':
                    num = s[l:r]
                    curr.add(NestedInteger(int(num)))
                l = r + 1
        
        return curr

Complexity

⏰ Time complexity: O(n), where n is the length of the input string, as each character in the string is processed exactly once
🧺 Space complexity: O(n)

Problem#

Examples#

Solution#

Method 1 - Using Stack#

Code#

Complexity#