Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

String is non-empty.
String does not contain white spaces.
String contains only digits 0-9, [, - ,, ].
Example 1:

Given s = “324”,

You should return a NestedInteger object which contains a single integer 324.
Example 2:

Given s = “[123,[456,[789]]]”,

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.
    

O(n) time O(k) space

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
56
57
58
59
60
 /**
* // 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 null if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/

public class Solution {
public NestedInteger deserialize(String s) {
if (s == null || s.length() == 0) {
return null;
}
if (s.charAt(0) != '[') {
return new NestedInteger(Integer.parseInt(s));
}
Stack<NestedInteger> stack = new Stack<>();
NestedInteger cur = new NestedInteger();
stack.push(cur);
int start = 1; // 0 is [
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == '[') {
NestedInteger ni = new NestedInteger();
stack.peek().add(ni);
stack.push(ni);
start = i + 1;
} else if (s.charAt(i) == ',' || s.charAt(i) == ']') {
if (i > start) {
Integer value = Integer.parseInt(s.substring(start, i));
stack.peek().add(new NestedInteger(value));
}
start = i + 1;
if (s.charAt(i) == ']') {
stack.pop();
}
}
}
return cur;
}
}