O(n) time complexity Java solution using Stack.


  • 0
    O
    
        public NestedInteger deserialize(String s) {
            Stack<NestedInteger> stack = new Stack<NestedInteger>();
            int sign = 1, num, step = 10, i = 0;
            char ch;
            NestedInteger tmp = null, parent = null;
            while(i < s.length()) {
                tmp = null;
                parent = null;
            	ch = s.charAt(i);
                if (ch == ']') {
                    tmp = stack.pop();
                    if (!stack.isEmpty()) {
                        parent = stack.pop();
                        parent.add(tmp);
                        stack.push(parent);
                    } else {
                        stack.push(tmp);
                    }
                } else if (ch == '-') {
                    sign = -1; 
                } else if(ch == '[') {
                    stack.push(new NestedInteger());
                } else if (ch-48 >= 0 && ch-48 <= 9) {
                    num = (ch-48);
                    i++;
                    while(i < s.length()) {
                    	ch = s.charAt(i);
                    	if (ch-48 >= 0 && ch-48 <= 9){
                    		num = num*step + (ch-48); 
                    	} else {
                    		break;
                    	}
                    	i++;
                    }
                    i--;
                    System.out.println(s.charAt(i));
                    if (!stack.isEmpty()) {
                        tmp = stack.pop();
                        tmp.add(new NestedInteger(num*sign));
                        stack.push(tmp);
                    } else {
                        stack.push(new NestedInteger(num*sign));
                    }
                    sign = 1;
                }
                i++;
            }
            return stack.pop();
        }
    

Log in to reply
 

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