Share my 18ms C++ code with non-recursive method


  • 0
    C

    The main idea is using a stack to store the status of the original recursive function.

    class Solution {
    struct status{ // a structure to store the recursive function
        int begin;
        int swapNode; 
        int timesPop; //if this status has been poped twice, it will never be pushed into the stack again.
        status(int n1 = 0, int n2 = 0, int n3 = 0):begin(n1),swapNode(n2),timesPop(n3){}
    };
    public:
    vector<vector<int> > permute(vector<int> &num) 
    {
        status cur;
        stack<status> s;
        vector<vector<int> > res;
        for(cur.swapNode = 0; cur.swapNode < num.size(); ++cur.swapNode)s.push(cur);//here initiate the original statement. 
        while(!s.empty()){
            cur = s.top();s.pop();
            if(cur.begin == num.size()-1)res.push_back(num);
            else{
                swap(num[cur.begin],num[cur.swapNode]);
                if(!cur.timesPop){
                    s.push(status(cur.begin++, cur.swapNode, cur.timesPop+1));
                    for(cur.swapNode = cur.begin; cur.swapNode<num.size() ;++cur.swapNode)s.push(cur);
                }
            }
        }
        return res;
    }
    };

Log in to reply
 

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