In this guide, you will get 385. Mini Parser LeetCode Solution with the best time and space complexity. The solution to Mini Parser problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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
Constraints:
1 <= s.length <= 5 * 104
s consists of digits, square brackets "[]", negative sign '-', and commas ','.
s is the serialization of valid NestedInteger.
All the values in the input are in the range [-106, 106].
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
385. Mini Parser LeetCode Solution in C++
class Solution {
public:
NestedInteger deserialize(string s) {
if (s[0] != '[')
return NestedInteger(stoi(s));
stack<NestedInteger> stack;
int start; // the start index of a number
for (int i = 0; i < s.length(); ++i) {
switch (s[i]) {
case '[':
stack.push(NestedInteger());
start = i + 1;
break;
case ',':
if (i > start) {
const int num = stoi(s.substr(start, i));
stack.top().add(NestedInteger(num));
}
start = i + 1;
break;
case ']':
NestedInteger popped = stack.top();
stack.pop();
if (i > start) {
const int num = stoi(s.substr(start, i));
popped.add(NestedInteger(num));
}
if (stack.empty())
return popped;
else
stack.top().add(popped);
start = i + 1;
break;
}
}
throw;
}
}; /* code provided by PROGIEZ */
385. Mini Parser LeetCode Solution in Java
class Solution {
public NestedInteger deserialize(String s) {
if (s.charAt(0) != '[')
return new NestedInteger(Integer.parseInt(s));
Deque<NestedInteger> stack = new ArrayDeque<>();
int start; // the start index of a number
for (int i = 0; i < s.length(); ++i)
switch (s.charAt(i)) {
case '[':
stack.push(new NestedInteger());
start = i + 1;
break;
case ',':
if (i > start) {
final int num = Integer.parseInt(s.substring(start, i));
stack.peek().add(new NestedInteger(num));
}
start = i + 1;
break;
case ']':
NestedInteger popped = stack.pop();
if (i > start) {
final int num = Integer.parseInt(s.substring(start, i));
popped.add(new NestedInteger(num));
}
if (!stack.isEmpty())
stack.peek().add(popped);
else
return popped;
start = i + 1;
break;
}
throw new IllegalArgumentException();
}
} // code provided by PROGIEZ
385. Mini Parser LeetCode Solution in Python
class Solution:
def deserialize(self, s: str) -> NestedInteger:
if s[0] != '[':
return NestedInteger(int(s))
stack = []
for i, c in enumerate(s):
if c == '[':
stack.append(NestedInteger())
start = i + 1
elif c == ',':
if i > start:
num = int(s[start:i])
stack[-1].add(NestedInteger(num))
start = i + 1
elif c == ']':
popped = stack.pop()
if i > start:
num = int(s[start:i])
popped.add(NestedInteger(num))
if stack:
stack[-1].add(popped)
else:
return popped
start = i + 1 # code by PROGIEZ
