Fun... Iterative Java + Clear Explanation


  • 0
    S

    I actually quite enjoyed this one... really helped cement using stacks for these type of nested applications for me.

    Just takes some reading + thinking to grasp this shitty, shitty dual data structure.

    Here's how it works in brief + some edge cases:

    1. Have a stack of NestedIntegers
    2. Go through all characters
    3. If a character is a digit, then go until the end of the digit. (Remember to account for negative #s.) At this point if the stack is empty, throw it on the stack.
      If not, then peek the current list and add it to the list (in the form of a new NestedInteger).
      Remember to handle the counter to prevent a double counter issue (non-obvious sometimes because it doesn't show up if there's a comma, but will show up on a close bracket.
    4. If the character is an open bracket, just add an empty NestedInteger to the stack
    5. If the character is a close bracket, if there is more than 1 element on the stack then pop the last and add it to the previous NestedInteger's list.
      This is what makes all the nesting magic function. If the stack has only 1 item, don't touch it -- this is the terminal item.
    6. Remember to increment the counter.
    7. After the end of the string, pop off the only remaining NestedInteger and return it.
    class Solution {
        
        public NestedInteger deserialize(String s) {
            
            int count = 0;
            
            Stack<NestedInteger> vals = new Stack<NestedInteger>();
                    
            while(count < s.length()){
                
                // If num, if open bracket, if close bracket
                
                char currentChar = s.charAt(count);
                
                if(Character.isDigit(currentChar) || currentChar == '-'){
                    
                    // Create a digit
                    
                    int start = count;
                    
                    while(count < s.length() && (Character.isDigit(s.charAt(count)) || s.charAt(count) == '-')){
                        
                        count++;
                        
                    }
                    
                    int val = Integer.parseInt(s.substring(start, count));
                    
                    if(vals.size() == 0){
                        
                        vals.push(new NestedInteger(val));
                        
                    }else{
                        
                        vals.peek().add(new NestedInteger(val));
                        
                    }
                    
                    count--;
                    
                }else if(currentChar == '['){
                    
                    // Create a new list thingy
                    // Check there's something in it -- if so, then create an empty nestedinteger
                    
                    // Detect if this is a subset
                    
                    vals.push(new NestedInteger());
    
                }else if(currentChar == ']'){
                    
                    if(vals.size() > 1){
                    
                        NestedInteger temp = vals.pop();
    
                        vals.peek().add(temp);
    
                    }
                    
                }
                
                count++;
                
            }
            
            return vals.pop();
            
        }
        
    }

Log in to reply
 

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