A detail-explained recursive solution without using stack


  • 0
    E
    public class Solution {
        public NestedInteger deserialize(String s) {
            return deserialize(s, new int[]{0});
        }
        
        //Use this function to deserialize a substring starting from index[0] 
        //this substring could either be a pure number(composing of "[\-0-9]")
        //or a list which starts with '[' and ends with ']'.
        //update the index to the next char before exiting.
        public NestedInteger deserialize(String s, int[] index) {
            NestedInteger ret = null;   //either the number or the list
            NestedInteger current = null;  //points to current element if it's a list
            StringBuilder sb = new StringBuilder(); //accumulating all numbers
            
            int i = index[0]; //starting from index[0]
            while(i<s.length()){
                char c = s.charAt(i);
                if((c>='0' && c<='9') || c == '-')
                    sb.append(c);
                else if(c == ',' || c == ']') {
                    if(current != null) { //it is a list, and current is assigned from [...]
                        ret.add(current);
                        current = null;
                    }
                    else if(sb.length() > 0) {
                        int number = Integer.valueOf(sb.toString());
                        sb.setLength(0);
                        if(ret == null) //it is a number
                            ret = new NestedInteger(number);
                        else //it is a list, and current element is from integers
                            ret.add(new NestedInteger(number));
                    }
                
                    if(c == ']') { //this ']' is for closing current substring when it's a list
                        index[0] = i+1; //points to next char
                        return ret;
                    }
                }
                else if(c == '[') {
                    if(ret == null)
                        ret = new NestedInteger(); //creating a new list
                    else { //entering an element of current list
                        int[] next = new int[]{i}; //$next points to a '['
                        current = deserialize(s, next); //now $next points to a char after ']'
                        i = next[0];
                        continue;
                    }
                }
                ++i;
            }
            
            index[0] = s.length();
            if(ret == null) {
                int number = Integer.valueOf(sb.toString());
                ret = new NestedInteger(number);
            }
            return ret;
        }
    }
    

Log in to reply
 

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