Problem
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:
An integer containing value 123.
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.
Solution
/**
* // 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();
* }
*/
Implementation:
class Solution {
public NestedInteger deserialize(String s) {
NestedInteger res = new NestedInteger();
if (s == null || s.length() == 0) return res;
if (s.charAt(0) != ‘[‘) res.setInteger(Integer.parseInt(s));
else if (s.length() > 2) {
int i = 1, count = 0, j = 1;
while (j < s.length()) {
char ch = s.charAt(j);
if (count == 0 && (ch == ‘,’ || j == s.length()-1)) {
NestedInteger cur = deserialize(s.substring(i, j));
res.add(cur);
i = j+1;
}
else if (ch == ‘[‘) count++;
else if (ch == ‘]’) count–;
j++;
}
}
return res;
}
}