"Double points + recursive" solution beats 92.90% of java submissions with full explanation


  • 0
    L

    Your runtime beats 92.90% of java submissions.
    57 / 57 test cases passed.
    Status: Accepted
    Runtime: 15 ms

        /*
        Valid forms of inputs:
        - a single number. e.g. "123"
        - a list of elements. e.g. "[123, 456]"
        - an empty list. e.g. "[]"
    
        Invalid forms of inputs:
        - A list of elements but without outermost brackets.
            e.g. "123,456", "123,[456]"
         */
    
    public NestedInteger deserialize(String s) {
            return parse(s.toCharArray(), 0, s.length() -1);
        }
    
        private NestedInteger parse(char[] chars, int from, int to){
            NestedInteger ni = new NestedInteger();
    
            if(chars[from] == '[' && chars[to] ==']') {
                //Current NestedInteger is a form of list
                //Remove the outermost square brackets.
                from++;
                to--;
            } else {
                //Current NestedInteger is a single Integer
                ni.setInteger(parseInteger(chars, from, to+1));
                return ni;
            }
    
            int stackCount = 1, value;
            for (int j=from; j<=to; j++) {
                if(chars[j] =='[') {
                    from = j;  //the start of a new list
    
                    while (++j<=to) {
                        if(chars[j] =='[') stackCount++;    //Act as stack.push('[')
                        if(chars[j] ==']') --stackCount;    //Act as stack.pop()
    
                        //At the end of a nested list
                        if (stackCount == 0) {
                            ni.add(parse(chars, from, j));
    
                            //Reset data for searching the next element
                            //1) skip the followed by comma, e.g. "],"
                            j++;
                            from=j+1;  //i point to the start point of next element
    
                            //2) Reset stackCount to preparing for parsing the next element
                            stackCount = 1;
                            break;
                        }
                    }
                } else if(chars[j] ==','/*middle elem*/ || j==to /*last elem in list*/) {
                    NestedInteger elem = new NestedInteger();
                    //handle the corner case: j==to
                    j = j==to? j+1: j;
                    value = parseInteger(chars, from, j);
                    elem.setInteger(value);
                    //Add the new element into list
                    ni.add(elem);
                    //Reset i
                    from=j+1;
                }
            }
            return ni;
        }
    
        private int parseInteger(char[] chars, int from, int to) {
            int value = Integer.valueOf(new String(Arrays.copyOfRange(chars, from, to)));
            return value;
        }
    

  • 0
    L

Log in to reply
 

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