# Java O(n) recursive solution

• The trick here is to recursively tackle the problem. Whenever a new list opens with "[" we go one step deeper into the recursion and return the index where we left to ensure the O(N) runtime.

For each character we check if it is a digit or any of the special characters. If it is a digit, we just add it to the current number. If it is a "-" we have to adjust the sign. Whenever we reach a "[" we create a new NestedInteger object and recurse. Whenever we reach a "]" we are done with the current recursion. We just have to add the last number to the list and return.

``````public NestedInteger deserialize(String s) {
NestedInteger result = new NestedInteger();
if (s == null || s.isEmpty()) {
return result;
}

deserialize(0, result, s);
return result;
}

private int deserialize(int index, NestedInteger current, String s) {
if (index >= s.length()) {
return index;
}

int currentNum = Integer.MIN_VALUE;
int sign = 1;
while(index < s.length()) {
char c = s.charAt(index);
if (c == '-') {
sign = -1;
} else if (isNumber(c)) {
currentNum = addNumber(currentNum == Integer.MIN_VALUE ? 0 : currentNum, c - '0');
} else if (c == ']' || c == ',') {
if (currentNum != Integer.MIN_VALUE) {
sign = 1;
currentNum = Integer.MIN_VALUE;
}

if (c == ']') {
return index;
}
} else if (c == '[' && index != 0) {
NestedInteger nested = new NestedInteger();
index = deserialize(index + 1, nested, s);
}

index++;
}

if ((current.getList() == null || current.getList().isEmpty()) && currentNum != Integer.MIN_VALUE) {
current.setInteger(currentNum * sign);
}

return index;
}

private boolean isNumber(char c) {
return Character.isDigit(c);
}

private int addNumber(int a, int b) {
return a * 10 + b;
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.