C++ 28ms beats 95% submissions as of 06/29/2016


  • 0
    R

    The main idea is to maintain the current state while recursively iterating over the nested structure. If we were to implement a recursion method (say printNested) that prints all integers. We just need to pass in current list every time:

    printNested(c){
       if(!c.isInteger()) printNested(c.getList());
       else cout<<c.getInteger()<<endl; //consume the number
    } 
    

    The above method can be easily written as iterative form using stack to simulate recursive function calls. Then you can further break the iterative method down to hasnext and next methods. Note, in order to get good performance, pointer is highly recommended. It is way faster than copying vectors over and over.

    Solution is attached below:

    class NestedIterator {
    public:
        stack<pair<vector<NestedInteger>*, int> > s;
        vector<NestedInteger>* v;
        int i;
        NestedIterator(vector<NestedInteger> &nestedList) {
            i = 0;
            v = &nestedList;
        }
    
        int next() {
            return (*v)[i++].getInteger();
        }
    
        bool hasNext() {
            while(1) {
                if(v->size() <= i) {
                    if(s.empty()) return false;
                    i = s.top().second;
                    v = s.top().first;
                    s.pop();
                }else { //v->size() > i
                    if(!(*v)[i].isInteger()){ // nested list,
                        s.push(make_pair(v, i+1)); // then save current state
                        v = &((*v)[i].getList()); // and go deeper
                        i = 0;
                    }else{
                        return true;
                    }
                }
            }
        }
    };

Log in to reply
 

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