## Sunday, August 14, 2016

### LeetCode 385 - Mini Parser

https://www.hrwhisper.me/leetcode-mini-parser/
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.
```
X. Using Stack
https://discuss.leetcode.com/topic/54270/an-java-iterative-solution/
Actually instead of using `substring()` to parse the integer, we could iteratively construct the number. The other parts are the same.
https://segmentfault.com/a/1190000007394571

``````public NestedInteger deserialize(String s) {
// check the input string first;
// .... if(s == null) return ..null
char[] arr = s.toCharArray();
if(arr[0] != '[') return new NestedInteger(Integer.parseInt(s));
Stack<NestedInteger> stack = new Stack<>();
for(int i = 0; i < arr.length; i ++) {
char ch = arr[i];
if(ch == '[') {
stack.push(new NestedInteger());
}
else if(ch == ']' && stack.size() > 1) {
NestedInteger top = stack.pop();
}
else if(Character.isDigit(ch) || ch == '-') {
boolean pos = true;
if(ch == '-') pos = false;
int num = 0;
while(i < arr.length && Character.isDigit(arr[i])) {
num *= 10;
num += arr[i] - '0';
i ++;
}
// move i back to the integer, [788],
// otherwise will skip the ']'
i --;
}
}
return stack.pop();
}``````
https://discuss.leetcode.com/topic/54270/an-java-iterative-solution
This approach will just iterate through every char in the string (no recursion).
• If encounters '[', push current NestedInteger to stack and start a new one.
• If encounters ']', end current NestedInteger and pop a NestedInteger from stack to continue.
• If encounters ',', append a new number to curr NestedInteger, if this comma is not right after a brackets.
• Update index l and r, where l shall point to the start of a integer substring, while r shall points to the end+1 of substring.
``````public NestedInteger deserialize(String s) {
if (s.isEmpty())
return null;
if (s.charAt(0) != '[') // ERROR: special case
return new NestedInteger(Integer.valueOf(s));

Stack<NestedInteger> stack = new Stack<>();
NestedInteger curr = null;
int l = 0; // l shall point to the start of a number substring;
// r shall point to the end+1 of a number substring
for (int r = 0; r < s.length(); r++) {
char ch = s.charAt(r);
if (ch == '[') {
if (curr != null) {
stack.push(curr);
}
curr = new NestedInteger();
l = r+1;
} else if (ch == ']') {
String num = s.substring(l, r);
if (!num.isEmpty())
if (!stack.isEmpty()) {
NestedInteger pop = stack.pop();
curr = pop;
}
l = r+1;
} else if (ch == ',') {
if (s.charAt(r-1) != ']') {
String num = s.substring(l, r);
}
l = r+1;
}
}

return curr;
}``````
Review
``````    public NestedInteger deserialize(String s) {
if (!s.startsWith("[")) {
return new NestedInteger(Integer.valueOf(s));
}
Stack<NestedInteger> stack = new Stack<>();
NestedInteger res = new NestedInteger();
stack.push(res);
int start = 1;
for (int i = 1; i < s.length(); i ++) {
char c = s.charAt(i);
if (c == '[') {
NestedInteger ni = new NestedInteger();
stack.push(ni);
start = i + 1;
} else if (c == ',' || c == ']') {
if (i > start) {
Integer val = Integer.valueOf(s.substring(start, i));
}
start = i + 1;
if (c == ']') {
stack.pop();
}
}
}
return res;
}``````
http://www.programcreek.com/2014/08/leetcode-mini-parser-java/
http://blog.csdn.net/yeqiuzs/article/details/52208388
```public NestedInteger deserialize(String s) {

Stack<NestedInteger> stack = new Stack<NestedInteger>();
String temp = "";

for(char c: s.toCharArray()){
switch(c){
case '[':
stack.push(new NestedInteger()); //start a new NI
break;

case ']':
if(!temp.equals("")){
temp="";
}

NestedInteger top = stack.pop();
if(!stack.empty()){
}else{
}

break;

case ',':
if(!temp.equals("")){
temp="";
}

break;

default:
temp += c;
}
}

if(!temp.equals("")){
return new NestedInteger(Integer.parseInt(temp));
}

return null;
}```

http://wisim.me/leetcode/2016/08/18/LeetCode_MinParser.html

Use StringBuilder
http://www.jianshu.com/p/4578be7c2270
``````    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> st = new Stack<NestedInteger>();
String temp = "";
for (int i = 0; i < s.length(); i++) {
char curr = s.charAt(i);
switch (curr) {
case '[':
st.push(new NestedInteger());
break;
case ']':
if (temp.length() != 0) {
temp = "";
}
if (st.size() > 1) {
NestedInteger node = st.pop();
}
break;
case ',':
if (temp.length() != 0) {
temp = "";
}
break;
default:
temp = temp + curr;
break;
}
}

return st.pop();
}``````
http://buttercola.blogspot.com/2015/11/airbnb-mini-parser.html
http://yuanhsh.iteye.com/blog/2230314
`  ``private` `static` `class` `NestedIntList {`
`    ``private` `int` `value;`
`    ``private` `boolean` `isNumber;`
`    ``private` `List<NestedIntList> intList;`
`    `
`    ``// Constructor to construct a number `
`    ``public` `NestedIntList(``int` `value) {`
`      ``this``.value = value;`
`      ``isNumber = ``true``;`
`    ``}`
`    `
`    ``// Constructor to construct a list`
`    ``public` `NestedIntList() {`
`      ``intList = ``new` `ArrayList<>();`
`      ``isNumber = ``false``;`
`    ``}`
`    `
`    ``public` `void` `add(NestedIntList num) {`
`      ``this``.intList.add(num);`
`    ``}`
`    `
`    ``public` `NestedIntList miniParser(String s) {`
`      ``if` `(s == ``null` `|| s.length() == ``0``) {`
`        ``return` `null``;`
`      ``}`
`      `
`      ``// Corner case "123"`
`      ``if` `(s.charAt(``0``) != ``'['``) {`
`        ``int` `num = Integer.parseInt(s);`
`        ``return` `new` `NestedIntList(num);`
`      ``}`
`      `
`      ``int` `i = ``0``;`
`      ``int` `left = ``1``;`
`      ``Stack<NestedIntList> stack = ``new` `Stack<>();`
`      ``NestedIntList result = ``null``;`
`      `
`      ``while` `(i < s.length()) {`
`        ``char` `c = s.charAt(i);`
`        ``if` `(c == ``'['``) {`
`          ``NestedIntList num = ``new` `NestedIntList();`
`          ``if` `(!stack.isEmpty()) {`
`            ``stack.peek().add(num);`
`          ``}`
`          ``stack.push(num);`
`          ``left = i + ``1``;`
`        ``} ``else` `if` `(c == ``','` `|| c == ``']'``) {`
`          ``if` `(left != i) {`
`            ``int` `value = Integer.parseInt(s.substring(left, i));`
`            ``NestedIntList num = ``new` `NestedIntList(value);`
`            ``stack.peek().add(num);`
`          ``}`
`          ``left = i + ``1``;`
`          `
`          ``if` `(c == ``']'``) {`
`            ``result = stack.pop();`
`          ``}`
`        ``}`
`        `
`        ``i++;`
`      ``}`
`      `
`      ``return` `result;`
`    ``}`
`    `
`    ``public` `String toString() {`
`      ``if` `(``this``.isNumber) {`
`        ``return` `this``.value + ``""``;`
`      ``} ``else` `{`
`        ``return` `this``.intList.toString();`
`      ``}`
`    ``}`
`  ``}`

http://blog.csdn.net/yeqiuzs/article/details/52208388

1. public NestedInteger deserialize(String s) {
2.     Stack<NestedInteger> stack = new Stack<NestedInteger>();
3.     String tokenNum = "";
4.
5.     for (char c : s.toCharArray()) {
6.         switch (c) {
7.         case '['://[代表一个list
8.             stack.push(new NestedInteger());
9.             break;
10.         case ']'://list结尾
11.             if (!tokenNum.equals(""))//前面token为数字
13.             NestedInteger ni = stack.pop();//本层list结束
14.             tokenNum = "";
15.             if (!stack.isEmpty()) {//栈内有更高层次的list
17.             } else {//栈为空，遍历到字符串结尾
18.                 return ni;
19.             }
20.             break;
21.         case ',':
22.             if (!tokenNum.equals("")) //将数字加入到本层list中
24.             tokenNum = "";
25.             break;
26.         default:
27.             tokenNum += c;
28.         }
29.     }
30.     if (!tokenNum.equals(""))//特殊case: 如果字符串只包含数字的情况
31.         return new NestedInteger(Integer.parseInt(tokenNum));
32.     return null;
33. }

```    NestedInteger deserialize(string s) {
if (s.empty()) return NestedInteger();
if (s[0] != '[') return NestedInteger(stoi(s));
stack<NestedInteger> st;
int start = 1;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '[') {
st.push(NestedInteger());
start = i + 1;
} else if (s[i] == ',' || s[i] == ']') {
if (i > start) {
}
start = i + 1;
if (s[i] == ']') {
if (st.size() > 1) {
NestedInteger t = st.top(); st.pop();
}
}
}
}
return st.top();
}```
X. Recursive Version
https://discuss.leetcode.com/topic/54277/short-java-recursive-solution/2
``````    public NestedInteger deserialize(String s) {
NestedInteger ret = new NestedInteger();
if (s == null || s.length() == 0) return ret;
if (s.charAt(0) != '[') {
ret.setInteger(Integer.parseInt(s));
}
else if (s.length() > 2) {
int start = 1, count = 0;
for (int i = 1; i < s.length(); i++) {
char c = s.charAt(i);
if (count == 0 && (c == ',' || i == s.length() - 1)) {
start = i + 1;
}
else if (c == '[') count++;
else if (c == ']') count--;
}
}
return ret;
}``````
https://discuss.leetcode.com/topic/54407/java-recursive-solution-one-scan-clean-easy-to-understand
1. if '[', construct a new NestedInteger;
2. if ']', add the number before ']' if it exists, the character before ']' must be a number or ']';
3. if ',', add the number before ',' if it exists, the character before ',' must be a number or ']';
4. if a number, just add the right pointer.
``````    public NestedInteger deserialize(String s) {
if (s.charAt(0) != '[') return new NestedInteger(Integer.parseInt(s));
NestedInteger result = new NestedInteger();
helper(s, 1, result);
return result;
}

private int helper(String s, int idx, NestedInteger parent) {
int l = idx, r = idx;
while (r < s.length()) {
String num = s.substring(l, r);//don't do here
if (s.charAt(r) == '[') {
NestedInteger child = new NestedInteger();
r = helper(s, r + 1, child);
l = r;
} else if (s.charAt(r) == ']') { // get num here
return r + 1;
} else if (s.charAt(r) == ',') {//get num here
r++;
l = r;
} else {
r++;
}
}
return s.length();
}``````
http://www.cnblogs.com/grandyang/p/5771434.html

```    NestedInteger deserialize(string s) {
if (s.empty()) return NestedInteger();
if (s[0] != '[') return NestedInteger(stoi(s));
if (s.size() <= 2) return NestedInteger();
NestedInteger res;
int start = 1, cnt = 0;
for (int i = 1; i < s.size(); ++i) {
if (cnt == 0 && (s[i] == ',' || i == s.size() - 1)) {
start = i + 1;
} else if (s[i] == '[') ++cnt;
else if (s[i] == ']') --cnt;
}
return res;
}```

X. Recursive version 2
https://discuss.leetcode.com/topic/59029/short-and-clean-java-recursive-solution-with-explanation
Using the "lvl" variable to track if we are inside an inner integer.
Using lIndex to track the leftmost start position.
Every time the program hit the "[" increase lvl, and decrease lvl when hit "]"
When the program meets ","
If lvl != 0, ignore the "," since we are inside a nested integer
else do recursive call ,add the result to the current list and move lIndex.
[ [abc, [xy]] , def, [qqq] ]
``````public NestedInteger deserialize(String s) {
if (s.length() == 0)    return new NestedInteger();
return myDeserialize(s, 0, s.length()-1);
}

private NestedInteger myDeserialize(String s, int start, int end) {
if (s.charAt(start) != '[')
return new NestedInteger(Integer.valueOf(s.substring(start, end+1)));

NestedInteger ni = new NestedInteger();
int lvl = 0, lIndex = start+1;

for (int i=start+1 ; i<=end-1 ; ++i) {
char ch = s.charAt(i);
if (ch == '[')  ++lvl;
else if (ch == ']') --lvl;
else if (ch == ',' && lvl == 0) {
lIndex = i + 1;
}
}
if (lIndex <= end-1) {
}
return ni;
}``````
https://discuss.leetcode.com/topic/54277/short-java-recursive-solution
Just for people who try this approach instead of stack. This takes much more time than stack as the depth of elements grow. If you would like to reduce time complexity, use stack as a space trade-off for time.
``````    public NestedInteger deserialize(String s) {
NestedInteger ret = new NestedInteger();
if (s == null || s.length() == 0) return ret;
if (s.charAt(0) != '[') {
ret.setInteger(Integer.parseInt(s));
}
else if (s.length() > 2) {
int start = 1, count = 0;
for (int i = 1; i < s.length(); i++) {
char c = s.charAt(i);
if (count == 0 && (c == ',' || i == s.length() - 1)) {
start = i + 1;
}
else if (c == '[') count++;
else if (c == ']') count--;
}
}
return ret;
}``````
https://discuss.leetcode.com/topic/55872/very-short-recursive-solution
``````    NestedInteger parse(string& s, int& i) {
if(s[i]=='[') {
++i;
NestedInteger list;
while(s[i] != ']') {
if(s[i] ==',') ++i;
}
++i;
return list;
} else {
int sum = 0;
int sign=1;
if(s[i] == '-'){ sign = -1; ++i;}
while(isdigit(s[i])) { sum *= 10; sum+= s[i]-'0'; ++i;}
return NestedInteger(sum*sign);
}
}
NestedInteger deserialize(string s) {
int i = 0;
return parse(s, i);
}``````
https://discuss.leetcode.com/topic/54274/java-10-ms-while-loop-recursion-one-scan

https://discuss.leetcode.com/topic/54268/straightforward-java-solution-with-explanation-and-a-simple-implementation-of-nestedinteger-for-your-ease-of-testing
``````class NestedInteger {
private List<NestedInteger> list;
private Integer integer;

public NestedInteger(List<NestedInteger> list){
this.list = list;
}

if(this.list != null){
} else {
this.list = new ArrayList();
}
}

public void setInteger(int num) {
this.integer = num;
}

public NestedInteger(Integer integer){
this.integer = integer;
}

public NestedInteger() {
this.list = new ArrayList();
}

public boolean isInteger() {
return integer != null;
}

public Integer getInteger() {
return integer;
}

public List<NestedInteger> getList() {
return list;
}

public String printNi(NestedInteger thisNi, StringBuilder sb){
if(thisNi.isInteger()) {
sb.append(thisNi.integer);
sb.append(",");
}
sb.append("[");
for(NestedInteger ni : thisNi.list){
if(ni.isInteger()) {
sb.append(ni.integer);
sb.append(",");
}
else {
printNi(ni, sb);
}
}
sb.append("]");
return sb.toString();
}
}``````