Nobody ever picks up the recursive way? Here it is. Simple and straightforward.


  • 0
    C
    private HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
    private void findMatchBrackets(String S){//We easily build all the valid pairs since we are assuming the input is valid.
        Stack<Character> charStack=new Stack<Character>();
        Stack<Integer> indexStack=new Stack<Integer>();
        char temp;
        for(int i=0;i<S.length();i++){
            temp=S.charAt(i);
            if(temp=='['){
                charStack.add('[');
                indexStack.add(i);
            }
            if(temp==']'){
                charStack.pop();
                map.put(indexStack.pop(),i);
            }
        }
    }
    public NestedInteger deserialize(String s) {
        if(s.length()==0)
        return new NestedInteger();
        findMatchBrackets(s);
        NestedInteger result=parseRecursive(s,0,s.length()-1);
        return result;
    }
    
    public NestedInteger parseRecursive(String s,int start,int end){
        if(s.charAt(start)!='[')  {//this is an Integer. Base case
            return new NestedInteger( Integer.parseInt( s.substring(start,end+1) ) );
        }
        String temp="";
        List<String> pieces=new ArrayList<String>();
        NestedInteger result=new NestedInteger();
        NestedInteger newOne;
        int startIndex,endIndex;
        char cur;
        for(int i=start+1;i<end;i++){
            cur=s.charAt(i);
            if(cur==','){
                pieces.add(temp);
                temp="";
            }
            else if(cur=='['){
                endIndex=map.get(i);
                temp=s.substring(i,endIndex+1);
                pieces.add(temp);
                i=endIndex+1;
                temp="";
            }
            else temp=temp+cur;
        }
        if(temp.length()>0) pieces.add(temp);
        startIndex=start+1;
        for(String piece:pieces){
            endIndex=startIndex+piece.length()-1;
            newOne=parseRecursive(s,startIndex,endIndex);
            result.add(newOne);
            startIndex=endIndex+2;
        }
        return result;
    }

Log in to reply
 

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