Java O(n) recursive solution


  • 0
    G

    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) {
                        current.add(new NestedInteger(currentNum * sign));
                        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);
                    current.add(nested);
                }
                
                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;
        }
    
    

Log in to reply
 

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