Mini Parser
Mini Parser is a medium stack problem solved with the stack basics pattern.
The best approach, optimal (one pass with a stack), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (split at top-level commas and recurse) up.
Problem
You are given a string s that describes a nested list of integers in bracket notation, for example "[7,[-12,[]],3]", or a single integer such as "-408". Parse it and return the corresponding NestedInteger object.
Each element of a nested list is either an integer or another nested list. You build the result with the provided NestedInteger class: NestedInteger() creates an empty list, NestedInteger(value) holds a single integer, add(ni) appends an element to a list, and setInteger(value) turns the object into a single integer. isInteger(), getInteger() and getList() read it back.
Examples
Example 1
- Input
s = "[7,[-12,[]],3]"- Output
[7,[-12,[]],3]- Why
- A list holding 7, a sub-list (with -12 and an empty list) and 3. The output shows the returned object written back in the same notation.
Example 2
- Input
s = "-408"- Output
-408- Why
- Without brackets the string is a single integer, so the result holds an integer, not a list.
Example 3
- Input
s = "[[[5]]]"- Output
[[[5]]]- Why
- The integer 5 wrapped in three levels of lists.
Constraints
1 <= s.length <= 5 * 10^4scontains only digits,'[',']','-'and',', with no spaces.sis a valid serialization of a nested integer list or of a single integer.- Every integer in
sis in the range[-10^6, 10^6].
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (split at top-level commas and recurse) | O(n · d) | O(n · d) |
| Optimal (one pass with a stack) | O(n) | O(n) |
1Brute force (split at top-level commas and recurse)
O(n · d)Each character is scanned and copied once per level of nesting around it, and d is the maximum depth.O(n · d)Substrings at every level of the recursion are alive at the same time.A valid string is either an integer or [ + comma-separated valid strings + ]. Strip the outer brackets, find the commas at bracket depth 0, and recursively deserialize every piece between them, adding each result to a new list.
- If
s[0]is not[, returnNestedInteger(parseInt(s)). - Take the body between the outer brackets and scan it with a depth counter (
[+1,]-1). - At each comma with depth 0, and at the end, deserialize the piece since the last cut and add it to the result list (skip empty pieces, which only occur for
[]).
class Solution {
public NestedInteger deserialize(String s) {
if (s.charAt(0) != '[') return new NestedInteger(Integer.parseInt(s));
NestedInteger list = new NestedInteger();
String body = s.substring(1, s.length() - 1);
int depth = 0, start = 0;
for (int i = 0; i <= body.length(); i++) {
if (i == body.length() || (body.charAt(i) == ',' && depth == 0)) {
if (i > start) list.add(deserialize(body.substring(start, i)));
start = i + 1;
} else if (body.charAt(i) == '[') {
depth++;
} else if (body.charAt(i) == ']') {
depth--;
}
}
return list;
}
}class Solution:
def deserialize(self, s: str) -> NestedInteger:
if s[0] != '[':
return NestedInteger(int(s))
result = NestedInteger()
body = s[1:-1]
depth, start = 0, 0
for i in range(len(body) + 1):
if i == len(body) or (body[i] == ',' and depth == 0):
if i > start:
result.add(self.deserialize(body[start:i]))
start = i + 1
elif body[i] == '[':
depth += 1
elif body[i] == ']':
depth -= 1
return resultclass Solution {
public:
NestedInteger deserialize(string s) {
if (s[0] != '[') return NestedInteger(stoi(s));
NestedInteger list;
string body = s.substr(1, s.size() - 2);
int depth = 0, start = 0, len = body.size();
for (int i = 0; i <= len; i++) {
if (i == len || (body[i] == ',' && depth == 0)) {
if (i > start) list.add(deserialize(body.substr(start, i - start)));
start = i + 1;
} else if (body[i] == '[') {
depth++;
} else if (body[i] == ']') {
depth--;
}
}
return list;
}
};function deserialize(s) {
if (s[0] !== '[') return new NestedInteger(parseInt(s, 10));
const list = new NestedInteger();
const body = s.substring(1, s.length - 1);
let depth = 0, start = 0;
for (let i = 0; i <= body.length; i++) {
if (i === body.length || (body[i] === ',' && depth === 0)) {
if (i > start) list.add(deserialize(body.substring(start, i)));
start = i + 1;
} else if (body[i] === '[') {
depth++;
} else if (body[i] === ']') {
depth--;
}
}
return list;
}2Optimal (one pass with a stack)
O(n)Every character is read once and every list is pushed and popped once.O(n)The stack holds at most d open lists, and the built structure has O(n) elements.Read the string left to right, keeping the lists that are still open on a stack. [ pushes a new empty list. A number (with an optional minus sign) is parsed in full and added to the list on top. ] pops the finished list and adds it to the list below it, or makes it the result if the stack is now empty. Commas carry no information.
- If
s[0]is not[, returnNestedInteger(parseInt(s)). - On
[: push a new emptyNestedInteger. - On
-or a digit: read the whole number and addNestedInteger(value)to the top list. - On
]: pop the top; if the stack is empty it is the result, else add it to the new top.
class Solution {
public NestedInteger deserialize(String s) {
if (s.charAt(0) != '[') return new NestedInteger(Integer.parseInt(s));
Deque<NestedInteger> stack = new ArrayDeque<>();
NestedInteger result = null;
int i = 0, n = s.length();
while (i < n) {
char c = s.charAt(i);
if (c == '[') {
stack.push(new NestedInteger());
i++;
} else if (c == ']') {
NestedInteger done = stack.pop();
if (stack.isEmpty()) result = done;
else stack.peek().add(done);
i++;
} else if (c == ',') {
i++;
} else {
int j = i + 1;
while (j < n && Character.isDigit(s.charAt(j))) j++;
stack.peek().add(new NestedInteger(Integer.parseInt(s.substring(i, j))));
i = j;
}
}
return result;
}
}class Solution:
def deserialize(self, s: str) -> NestedInteger:
if s[0] != '[':
return NestedInteger(int(s))
stack = []
result = None
i, n = 0, len(s)
while i < n:
c = s[i]
if c == '[':
stack.append(NestedInteger())
i += 1
elif c == ']':
done = stack.pop()
if not stack:
result = done
else:
stack[-1].add(done)
i += 1
elif c == ',':
i += 1
else:
j = i + 1
while j < n and s[j].isdigit():
j += 1
stack[-1].add(NestedInteger(int(s[i:j])))
i = j
return resultclass Solution {
public:
NestedInteger deserialize(string s) {
if (s[0] != '[') return NestedInteger(stoi(s));
vector<NestedInteger> stack;
NestedInteger result;
int i = 0, n = s.size();
while (i < n) {
char c = s[i];
if (c == '[') {
stack.push_back(NestedInteger());
i++;
} else if (c == ']') {
NestedInteger done = std::move(stack.back());
stack.pop_back();
if (stack.empty()) result = std::move(done);
else stack.back().add(done);
i++;
} else if (c == ',') {
i++;
} else {
int j = i + 1;
while (j < n && isdigit((unsigned char) s[j])) j++;
stack.back().add(NestedInteger(stoi(s.substr(i, j - i))));
i = j;
}
}
return result;
}
};function deserialize(s) {
if (s[0] !== '[') return new NestedInteger(parseInt(s, 10));
const stack = [];
let result = null;
let i = 0;
const n = s.length;
while (i < n) {
const c = s[i];
if (c === '[') {
stack.push(new NestedInteger());
i++;
} else if (c === ']') {
const done = stack.pop();
if (stack.length === 0) result = done;
else stack[stack.length - 1].add(done);
i++;
} else if (c === ',') {
i++;
} else {
let j = i + 1;
while (j < n && s[j] >= '0' && s[j] <= '9') j++;
stack[stack.length - 1].add(new NestedInteger(parseInt(s.substring(i, j), 10)));
i = j;
}
}
return result;
}Edge cases to test
- A bare integer, including a negative one
- An empty list
[], alone or nested - Deep nesting such as
[[[[1]]]] - Multi-digit and negative numbers next to brackets
Hints
Hint 1
If s does not start with [, it is one integer: wrap it with new NestedInteger(value).
Hint 2
Otherwise strip the outer brackets and cut the inside at commas that are not inside any deeper bracket; each piece is itself a valid serialization.
Hint 3
To avoid re-scanning substrings, read the string once with a stack: [ opens a new list, ] closes the top list and attaches it to the one below, and a number is added to the top list.
FAQ
What is the best time complexity for Mini Parser?
Optimal (one pass with a stack) runs in O(n) time and O(n) extra space. Every character is read once and every list is pushed and popped once.
Which pattern does Mini Parser use?
It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.
Is there a brute force solution for Mini Parser?
Yes. Brute force (split at top-level commas and recurse) takes O(n · d) time and O(n · d) space. A valid string is either an integer or [ + comma-separated valid strings + ].
Which edge cases should I test for Mini Parser?
A bare integer, including a negative one; An empty list [], alone or nested; Deep nesting such as [[[[1]]]]; Multi-digit and negative numbers next to brackets.