385. Mini Parser
Description
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].
Solutions
Solution 1: Recursion
We first judge whether the string $s$ is empty or an empty list. If so, simply return an empty NestedInteger. If $s$ is an integer, we simply return a NestedInteger containing this integer. Otherwise, we traverse the string $s$ from left to right. If the current depth is $0$ and we encounter a comma or the end of the string $s$, we take a substring and recursively call the function to parse the substring and add the return value to the list. Otherwise, if the current encounter is a left parenthesis, we increase the depth by $1$ and continue to traverse. If we encounter a right parenthesis, we decrease the depth by $1$ and continue to traverse.
After the traversal is over, return the answer.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string $s$.
Python3
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
# class NestedInteger:
# def __init__(self, value=None):
# """
# If value is not specified, initializes an empty list.
# Otherwise initializes a single integer equal to value.
# """
#
# def isInteger(self):
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# :rtype bool
# """
#
# def add(self, elem):
# """
# Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
# :rtype void
# """
#
# def setInteger(self, value):
# """
# Set this NestedInteger to hold a single integer equal to value.
# :rtype void
# """
#
# def getInteger(self):
# """
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# :rtype int
# """
#
# def getList(self):
# """
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# :rtype List[NestedInteger]
# """
class Solution:
def deserialize(self, s: str) -> NestedInteger:
if not s or s == '[]':
return NestedInteger()
if s[0] != '[':
return NestedInteger(int(s))
ans = NestedInteger()
depth, j = 0, 1
for i in range(1, len(s)):
if depth == 0 and (s[i] == ',' or i == len(s) - 1):
ans.add(self.deserialize(s[j:i]))
j = i + 1
elif s[i] == '[':
depth += 1
elif s[i] == ']':
depth -= 1
return ans
Java
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* public interface NestedInteger {
* // Constructor initializes an empty nested list.
* public NestedInteger();
*
* // Constructor initializes a single integer.
* public NestedInteger(int value);
*
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
* public boolean isInteger();
*
* // @return the single integer that this NestedInteger holds, if it holds a single integer
* // Return null if this NestedInteger holds a nested list
* public Integer getInteger();
*
* // Set this NestedInteger to hold a single integer.
* public void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* public void add(NestedInteger ni);
*
* // @return the nested list that this NestedInteger holds, if it holds a nested list
* // Return empty list if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
class Solution {
public NestedInteger deserialize(String s) {
if ("".equals(s) || "[]".equals(s)) {
return new NestedInteger();
}
if (s.charAt(0) != '[') {
return new NestedInteger(Integer.parseInt(s));
}
NestedInteger ans = new NestedInteger();
int depth = 0;
for (int i = 1, j = 1; i < s.length(); ++i) {
if (depth == 0 && (s.charAt(i) == ',' || i == s.length() - 1)) {
ans.add(deserialize(s.substring(j, i)));
j = i + 1;
} else if (s.charAt(i) == '[') {
++depth;
} else if (s.charAt(i) == ']') {
--depth;
}
}
return ans;
}
}
C++
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* public:
* // Constructor initializes an empty nested list.
* NestedInteger();
*
* // Constructor initializes a single integer.
* NestedInteger(int value);
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* bool isInteger() const;
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* int getInteger() const;
*
* // Set this NestedInteger to hold a single integer.
* void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* void add(const NestedInteger &ni);
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The result is undefined if this NestedInteger holds a single integer
* const vector<NestedInteger> &getList() const;
* };
*/
class Solution {
public:
NestedInteger deserialize(string s) {
if (s == "" || s == "[]") {
return NestedInteger();
}
if (s[0] != '[') {
return NestedInteger(stoi(s));
}
NestedInteger ans;
int depth = 0;
for (int i = 1, j = 1; i < s.size(); ++i) {
if (depth == 0 && (s[i] == ',' || i == s.size() - 1)) {
ans.add(deserialize(s.substr(j, i - j)));
j = i + 1;
} else if (s[i] == '[') {
++depth;
} else if (s[i] == ']') {
--depth;
}
}
return ans;
}
};
Go
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* type NestedInteger struct {
* }
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* func (n NestedInteger) IsInteger() bool {}
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* // So before calling this method, you should have a check
* func (n NestedInteger) GetInteger() int {}
*
* // Set this NestedInteger to hold a single integer.
* func (n *NestedInteger) SetInteger(value int) {}
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* func (n *NestedInteger) Add(elem NestedInteger) {}
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The list length is zero if this NestedInteger holds a single integer
* // You can access NestedInteger's List element directly if you want to modify it
* func (n NestedInteger) GetList() []*NestedInteger {}
*/
func deserialize(s string) *NestedInteger {
ans := &NestedInteger{}
if s == "" || s == "[]" {
return ans
}
if s[0] != '[' {
v, _ := strconv.Atoi(s)
ans.SetInteger(v)
return ans
}
depth := 0
for i, j := 1, 1; i < len(s); i++ {
if depth == 0 && (s[i] == ',' || i == len(s)-1) {
(*ans).Add(*deserialize(s[j:i]))
j = i + 1
} else if s[i] == '[' {
depth++
} else if s[i] == ']' {
depth--
}
}
return ans
}
TypeScript
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* If value is provided, then it holds a single integer
* Otherwise it holds an empty nested list
* constructor(value?: number) {
* ...
* };
*
* Return true if this NestedInteger holds a single integer, rather than a nested list.
* isInteger(): boolean {
* ...
* };
*
* Return the single integer that this NestedInteger holds, if it holds a single integer
* Return null if this NestedInteger holds a nested list
* getInteger(): number | null {
* ...
* };
*
* Set this NestedInteger to hold a single integer equal to value.
* setInteger(value: number) {
* ...
* };
*
* Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
* add(elem: NestedInteger) {
* ...
* };
*
* Return the nested list that this NestedInteger holds,
* or an empty list if this NestedInteger holds a single integer
* getList(): NestedInteger[] {
* ...
* };
* };
*/
function deserialize(s: string): NestedInteger {
if (s === '' || s === '[]') {
return new NestedInteger();
}
if (s[0] !== '[') {
return new NestedInteger(+s);
}
const ans: NestedInteger = new NestedInteger();
let depth = 0;
for (let i = 1, j = 1; i < s.length; ++i) {
if (depth === 0 && (s[i] === ',' || i === s.length - 1)) {
ans.add(deserialize(s.slice(j, i)));
j = i + 1;
} else if (s[i] === '[') {
++depth;
} else if (s[i] === ']') {
--depth;
}
}
return ans;
}
Solution 2: Stack
We can use a stack to simulate the recursive process.
We first judge whether the string $s$ is an integer. If so, we simply return a NestedInteger containing this integer. Otherwise, we traverse the string $s$ from left to right. For the character $c$ currently traversed:
If $c$ is a negative sign, we set the negative sign to
true;If $c$ is a number, we add the number to the current number $x$, where the initial value of $x$ is $0$;
If $c$ is a left parenthesis, we push a new
NestedIntegeronto the stack;If $c$ is a right parenthesis or comma, we judge whether the previous character of the current character is a number. If so, we add the current number $x$ to the top
NestedIntegerof the stack according to the negative sign, and then reset the negative sign tofalseand the current number $x$ to $0$. If $c$ is a right parenthesis and the size of the current stack is greater than $1$, we pop the topNestedIntegerof the stack and add it to the topNestedIntegerof the stack.
After the traversal is over, return the top NestedInteger of the stack.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string $s$.
Python3
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
# class NestedInteger:
# def __init__(self, value=None):
# """
# If value is not specified, initializes an empty list.
# Otherwise initializes a single integer equal to value.
# """
#
# def isInteger(self):
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# :rtype bool
# """
#
# def add(self, elem):
# """
# Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
# :rtype void
# """
#
# def setInteger(self, value):
# """
# Set this NestedInteger to hold a single integer equal to value.
# :rtype void
# """
#
# def getInteger(self):
# """
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# :rtype int
# """
#
# def getList(self):
# """
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# :rtype List[NestedInteger]
# """
class Solution:
def deserialize(self, s: str) -> NestedInteger:
if s[0] != '[':
return NestedInteger(int(s))
stk, x, neg = [], 0, False
for i, c in enumerate(s):
if c == '-':
neg = True
elif c.isdigit():
x = x * 10 + int(c)
elif c == '[':
stk.append(NestedInteger())
elif c in ',]':
if s[i - 1].isdigit():
if neg:
x = -x
stk[-1].add(NestedInteger(x))
x, neg = 0, False
if c == ']' and len(stk) > 1:
t = stk.pop()
stk[-1].add(t)
return stk.pop()
Java
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* public interface NestedInteger {
* // Constructor initializes an empty nested list.
* public NestedInteger();
*
* // Constructor initializes a single integer.
* public NestedInteger(int value);
*
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
* public boolean isInteger();
*
* // @return the single integer that this NestedInteger holds, if it holds a single integer
* // Return null if this NestedInteger holds a nested list
* public Integer getInteger();
*
* // Set this NestedInteger to hold a single integer.
* public void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* public void add(NestedInteger ni);
*
* // @return the nested list that this NestedInteger holds, if it holds a nested list
* // Return empty list if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
class Solution {
public NestedInteger deserialize(String s) {
if (s.charAt(0) != '[') {
return new NestedInteger(Integer.parseInt(s));
}
Deque<NestedInteger> stk = new ArrayDeque<>();
int x = 0;
boolean neg = false;
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (c == '-') {
neg = true;
} else if (Character.isDigit(c)) {
x = x * 10 + c - '0';
} else if (c == '[') {
stk.push(new NestedInteger());
} else if (c == ',' || c == ']') {
if (Character.isDigit(s.charAt(i - 1))) {
if (neg) {
x = -x;
}
stk.peek().add(new NestedInteger(x));
}
x = 0;
neg = false;
if (c == ']' && stk.size() > 1) {
NestedInteger t = stk.pop();
stk.peek().add(t);
}
}
}
return stk.peek();
}
}
C++
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* public:
* // Constructor initializes an empty nested list.
* NestedInteger();
*
* // Constructor initializes a single integer.
* NestedInteger(int value);
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* bool isInteger() const;
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* int getInteger() const;
*
* // Set this NestedInteger to hold a single integer.
* void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* void add(const NestedInteger &ni);
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The result is undefined if this NestedInteger holds a single integer
* const vector<NestedInteger> &getList() const;
* };
*/
class Solution {
public:
NestedInteger deserialize(string s) {
if (s[0] != '[') {
return NestedInteger(stoi(s));
}
stack<NestedInteger> stk;
int x = 0;
bool neg = false;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '-') {
neg = true;
} else if (isdigit(s[i])) {
x = x * 10 + s[i] - '0';
} else if (s[i] == '[') {
stk.push(NestedInteger());
} else if (s[i] == ',' || s[i] == ']') {
if (isdigit(s[i - 1])) {
if (neg) {
x = -x;
}
stk.top().add(NestedInteger(x));
}
x = 0;
neg = false;
if (s[i] == ']' && stk.size() > 1) {
auto t = stk.top();
stk.pop();
stk.top().add(t);
}
}
}
return stk.top();
}
};
Go
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* type NestedInteger struct {
* }
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* func (n NestedInteger) IsInteger() bool {}
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* // So before calling this method, you should have a check
* func (n NestedInteger) GetInteger() int {}
*
* // Set this NestedInteger to hold a single integer.
* func (n *NestedInteger) SetInteger(value int) {}
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* func (n *NestedInteger) Add(elem NestedInteger) {}
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The list length is zero if this NestedInteger holds a single integer
* // You can access NestedInteger's List element directly if you want to modify it
* func (n NestedInteger) GetList() []*NestedInteger {}
*/
func deserialize(s string) *NestedInteger {
if s[0] != '[' {
v, _ := strconv.Atoi(s)
ans := NestedInteger{}
ans.SetInteger(v)
return &ans
}
stk := []*NestedInteger{}
x := 0
neg := false
for i, c := range s {
if c == '-' {
neg = true
} else if c >= '0' && c <= '9' {
x = x*10 + int(c-'0')
} else if c == '[' {
stk = append(stk, &NestedInteger{})
} else if c == ',' || c == ']' {
if s[i-1] >= '0' && s[i-1] <= '9' {
if neg {
x = -x
}
t := NestedInteger{}
t.SetInteger(x)
stk[len(stk)-1].Add(t)
}
x = 0
neg = false
if c == ']' && len(stk) > 1 {
t := stk[len(stk)-1]
stk = stk[:len(stk)-1]
stk[len(stk)-1].Add(*t)
}
}
}
return stk[0]
}
TypeScript
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* If value is provided, then it holds a single integer
* Otherwise it holds an empty nested list
* constructor(value?: number) {
* ...
* };
*
* Return true if this NestedInteger holds a single integer, rather than a nested list.
* isInteger(): boolean {
* ...
* };
*
* Return the single integer that this NestedInteger holds, if it holds a single integer
* Return null if this NestedInteger holds a nested list
* getInteger(): number | null {
* ...
* };
*
* Set this NestedInteger to hold a single integer equal to value.
* setInteger(value: number) {
* ...
* };
*
* Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
* add(elem: NestedInteger) {
* ...
* };
*
* Return the nested list that this NestedInteger holds,
* or an empty list if this NestedInteger holds a single integer
* getList(): NestedInteger[] {
* ...
* };
* };
*/
function deserialize(s: string): NestedInteger {
if (s[0] !== '[') {
return new NestedInteger(+s);
}
const stk: NestedInteger[] = [];
let x = 0;
let neg = false;
for (let i = 0; i < s.length; ++i) {
if (s[i] === '-') {
neg = true;
} else if (s[i] === '[') {
stk.push(new NestedInteger());
} else if (s[i] >= '0' && s[i] <= '9') {
x = x * 10 + s[i].charCodeAt(0) - '0'.charCodeAt(0);
} else if (s[i] === ',' || s[i] === ']') {
if (s[i - 1] >= '0' && s[i - 1] <= '9') {
stk[stk.length - 1].add(new NestedInteger(neg ? -x : x));
}
x = 0;
neg = false;
if (s[i] === ']' && stk.length > 1) {
const t = stk.pop()!;
stk[stk.length - 1].add(t);
}
}
}
return stk[0];
}