Java Iterative Solution iterating through characters O(N) space and runtime


  • 0
    I
    1. Initialize first NestedInteger as list
    2. Iterate through every character
      a. if meet [, push new list to stack, since this is going to be list (keep only lists in stack)
      b. if meet ] , pop last list from stack and add to peek as element of previous list started
      c. if number, add to peek of stack, since we have only list ones in the stack
    3. Return the first element of original initial NestedInteger

    Runtime complexity: O(N) where N is the s.length()
    Space complexity: The worst case is the following manner of nesting: [X, [X, [X, [X...]]]], where it's number of integers as K, O(K) or can as well be said to be O(N) as an upper bound.

    public class Solution {
       public NestedInteger deserialize(String s) {
            
            Stack<NestedInteger> st = new Stack<NestedInteger>();
            st.push(new NestedInteger());
            
            for(int i = 0; i < s.length(); i++) {
                if(s.charAt(i) == '[') {
                    st.push(new NestedInteger());
                } else if(s.charAt(i) == ']') {
                    NestedInteger tmp = st.pop();
                    st.peek().add(tmp);
                } else if(s.charAt(i) == ',') {
                    continue;
                } else {
                    String num = "";
                    while(i < s.length() && (s.charAt(i) == '-' || Character.isDigit(s.charAt(i)))) {
                        num += s.charAt(i);
                        i++;
                    }
                    
                    st.peek().add(new NestedInteger(Integer.parseInt(num)));
                    i--;
                }
            }
            
            if(s.isEmpty()) {
                return null;
            }
            
            return st.peek().getList().get(0);
        }
    }
    

Log in to reply
 

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