Fun... Iterative Java + Clear Explanation

  • 0

    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) == '-')){
                    int val = Integer.parseInt(s.substring(start, count));
                    if(vals.size() == 0){
                        vals.push(new NestedInteger(val));
                        vals.peek().add(new NestedInteger(val));
                }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();
            return vals.pop();

Log in to reply

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