Algorithm
Problem Name: 385. Mini Parser
Problem Link: https://leetcode.com/problems/mini-parser/
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 * 104sconsists of digits, square brackets"[]", negative sign'-', and commas','.sis the serialization of validNestedInteger.- All the values in the input are in the range
[-106, 106].
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
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 leftIdx = 0;
for (int rightIdx = 0; rightIdx < s.length(); rightIdx++) {
if (s.charAt(rightIdx) == '[') {
if (curr != null) {
stack.push(curr);
}
curr = new NestedInteger();
leftIdx = rightIdx + 1;
} else if (s.charAt(rightIdx) == ']') {
String number = s.substring(leftIdx, rightIdx);
if (!number.isEmpty()) {
curr.add(new NestedInteger(Integer.parseInt(number)));
}
if (!stack.isEmpty()) {
NestedInteger popped = stack.pop();
popped.add(curr);
curr = popped;
}
leftIdx = rightIdx + 1;
} else if (s.charAt(rightIdx) == ',') {
if (s.charAt(rightIdx - 1) != ']') {
String number = s.substring(leftIdx, rightIdx);
curr.add(new NestedInteger(Integer.parseInt(number)));
}
leftIdx = rightIdx + 1;
}
}
return curr;
}
}
Input
s = "324"
Output
324
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const deserialize = function(s) {
const recursion = s => {
const re = new NestedInteger()
if (!s || s.length === 0) {
return re
}
if (s.charAt(0) !== '[') {
re.setInteger(parseInt(s, 10))
} else if (s.length > 2) {
let start = 1
let cnt = 0
for (let i = 1; i < s.length; i++) {
const char = s.charAt(i)
if (cnt === 0 && (char === ',' || i === s.length - 1)) {
re.add(recursion(s.substring(start, i)))
start = i + 1
} else if (char === '[') {
cnt++
} else if (char === ']') {
cnt--
}
}
}
return re
}
return recursion(s)
}
Input
s = "324"
Output
324
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def deserialize(self, s):
stack, num, last = [], "", None
for c in s:
if c.isdigit() or c == "-": num += c
elif c == "," and num:
stack[-1].add(NestedInteger(int(num)))
num = ""
elif c == "[":
elem = NestedInteger()
if stack: stack[-1].add(elem)
stack.append(elem)
elif c == "]":
if num:
stack[-1].add(NestedInteger(int(num)))
num = ""
last = stack.pop()
return last if last else NestedInteger(int(num))
Input
s = "[123,[456,[789]]]"
Output
[123,[456,[789]]]