Short and Clean Java Recursive Solution with Explanation


  • 3
    L

    Using the "lvl" variable to track if we are inside an inner integer.
    Using lIndex to track the leftmost start position.
    Every time the program hit the "[" increase lvl, and decrease lvl when hit "]"
    When the program meets ","
    If lvl != 0, ignore the "," since we are inside a nested integer
    else do recursive call ,add the result to the current list and move lIndex.

    [ [abc, [xy]] , def, [qqq] ]
    ni.add(myDeserialize("[abc, [xy]]"));
    ni.add(myDeserialize("def");
    ni.add(myDeserialize("[qqq]");

    public NestedInteger deserialize(String s) {
        if (s.length() == 0)    return new NestedInteger();
        return myDeserialize(s, 0, s.length()-1);
    }
    
    private NestedInteger myDeserialize(String s, int start, int end) {
        if (s.charAt(start) != '[') 
            return new NestedInteger(Integer.valueOf(s.substring(start, end+1)));
    
        NestedInteger ni = new NestedInteger();
        int lvl = 0, lIndex = start+1;
    
        for (int i=start+1 ; i<=end-1 ; ++i) {
            char ch = s.charAt(i);
            if (ch == '[')  ++lvl;
            else if (ch == ']') --lvl; 
            else if (ch == ',' && lvl == 0) {
                ni.add(myDeserialize(s, lIndex, i-1));
                lIndex = i + 1;
            }
        }
        if (lIndex <= end-1) {
            ni.add(myDeserialize(s, lIndex, end-1));
        }
        return ni;        
    }

  • 0

    this is really easy to understand, cool solution.


Log in to reply
 

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