Simple DFS style solution in C++ for Flatten Nested List Iterator


  • 0
    H

    Comments say it all

    struct PP { // vector of NestedInteger and next element to read in this vector
      public:
        vector<NestedInteger> first;
        int second;
        bool hasMore(){return second < first.size(); }
        PP(vector<NestedInteger>& i_nl, int i_nli){first=i_nl; second=i_nli;}
    };
    
    class NestedIterator {
        
        stack<PP> s; // stack of vector with our index positions in those
    
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            s.push(PP(nestedList, 0)); // Initially we are in the first vector at position 0.
        }
    
        int next() {  // Just get the element at top and increment our position forward
            s.top().second++;
            return s.top().first[s.top().second-1].getInteger();
        }
    
        bool hasNext() { 
    
    // If next element is integer, then return true, otherwise put reference of list element and position 0 
    // at top of the stack and continue check for stack top to become integer. If there are no more elements 
    // in this list then pop it out of the stack.
            
            while(s.size()!=0)
            {
                if (!(s.top().hasMore())) { s.pop(); continue;}
                
                if (s.top().first[s.top().second].isInteger()) return true;
                
                s.top().second++; 
                s.push(PP(s.top().first[s.top().second-1].getList(), 0));
            }
            
            return false;
        }
    };
    

  • 0

Log in to reply
 

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