Short Java solution - Easy to understand - Recursion - Less Code and Full of Explanation


  • 0
    K

    So basically, we first check if the first char is '[' or not, if it is, we know it is def a list, if it is NOT, then we know it is an integer. (Assume the input is valid).
    So if it is a list, we will create a NestedInteger, and add all its "items" one by one to this NestedInteger (of cuz, for each item, we recursively create NestedInteger and return), and finally return this NestedInteger.

    public NestedInteger deserialize(String s) {
        if(s == null || s.isEmpty()) return null;
        if(s.charAt(0) != '[') {
            ///This is a number!! - Easy
            return new NestedInteger(Integer.parseInt(s));
        }
        
        //this is a list
        NestedInteger res = new NestedInteger();
        //s = "[aaa, [bbb, ccc], dd]"
        s = s.substring(1, s.length()-1); //strip outter '[' and ']'
        //Stack is used to keep track of which ',' is the one we need to parse for this level.  
        //For example, the ',' after 'aaa', once we hit that, we know 'aaa' is an item, and we recursively deserialize 'aaa', but for '[bbb,ccc]' I want this as a whole part, cuz it as a whole is a NestedInteger which I wanna do a recursive call on, 
        //so once I met the ',' after 'bbb', I am not gonna do anything, I will just keep appending it to a string and later when I hit ',' after 'ccc', I am gonna send the whole '[bbb,ccc]' to the recursive call. 
        Stack<Character> stack = new Stack<>();
        String prev = "";    //keep track of the item in THIS level before ',' 
    
        // right now s: "aaa,[bbb,ccc],dd". cuz we strip the outter [ ]
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if(stack.isEmpty() && c == ',') {
                //if the stack is empty and then we hit ',', we know prev right now is a item for this level. 
               //If the stack is not empty, that means I am in inside parsing one of the item in this level, I haven't done yet. So I will wait to do recursive call.
                res.add(deserialize(prev));
                prev="";
            } else if(c == '['){
                stack.push(c);   //This is telling I am inside parsing one item in this level
                prev += c;
            } else if(c == ']') {
                stack.pop();     //def pop out here cuz later when we hit ',' after 'ccc', the stack should be empty, and we will do a recursive call on '[bbb,ccc]'
                prev += c;
            } else if(c>= '0' && c<='9' || c==',' || c=='-') {
                prev += c;
            }
        }
    
        res.add(deserialize(prev));   //don't forget the last item, cuz we don't have a ',' after the last item in the s
    
        return res;
    }

  • 0
    K

    It might not be as efficient as other iterative solution, since it scans the same substring several times, but I think the code is def more readable and easy to understand. Cuz recursion def helps us to make things easier.

    Welcome to post any feedback or comments!!


Log in to reply
 

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