C++ BFS plus DFS, why MLE


  • 1
    L

    At the beginning, I got TLE and I checked it here so the problem is do not go through the dict because it's too large. After I change it, I got MLE and I think my graph node only consists of a string and some pointers to its children. How can I shrink it further? By the way, is this the correct output for the most difficult instance? I can pass it on my laptop but MLE here.

    sand band bind bins bids aids ands ants ante anne acne 
    sand band bans bins bids aids ands ants ante anne acne 
    sand sane sine side aide aids ands ants ante anne acne 
    sand sane sade side aide aids ands ants ante anne acne 
    sand sans bans bins bids aids ands ants ante anne acne 
    sand sans kans kins kids aids ands ants ante anne acne 
    sand sans sins bins bids aids ands ants ante anne acne 
    sand sans sins kins kids aids ands ants ante anne acne 
    sand sans sins sims aims arms arts ants ante anne acne 
    sand sans sins sims aims aids ands ants ante anne acne 
    sand sans sins sirs airs aids ands ants ante anne acne
    
    class Solution 
    {
    public:
        class State
        {
        public:
            string s;
            vector<State*> child;
            //int depth;
            State(const string& s) : s(s) {}
        };
    
        void DFS(const State* node, vector<string>& local, vector<vector<string>>& res, string& end)
        {
            local.push_back(node->s);
            if(node->child.size()==0) // base case
            {
                if(node->s==end)
                {
                    if(res.size())
                    {
                        if(local.size()<res[0].size())
                        {
                            res.clear();
                            res.push_back(local);
                        }
                        else 
                        {
                            if(local.size()==res[0].size())
                                res.push_back(local);
                        }
                    }
                    else
                    {
                        res.push_back(local);
                    }
                }
            }
            else
            {
                for(auto it = node->child.begin();it!=node->child.end();it++)
                {
                    DFS(*it,local,res,end);
                }
                
            }
            local.pop_back();
        }
        vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) 
        {
            vector<queue<State*> > q(2,queue<State*>()); // two queue to build the search graph level by level
            int count=0;
            State* root = new State(start);
            q[0].push(root);
            vector<vector<string>> res;
            unordered_set<string> unvisited = dict;  // unvisited prevent circle in BFS
            unvisited.erase(start);
            vector<string> garbage;
            while(q[count%2].empty()==false) // build the search graph using BFS
            {
                State* front = q[count%2].front();
                q[count%2].pop();
                if(front->s==end)
                    break;
                for( int i = 0; i < front->s.size(); i++)
                {
                   string tmp(front->s);
                   for( char az = 'a'; az <= 'z'; az++)
                   {
                       tmp[i] = az;
                       if( front->s!=tmp&&unvisited.find(tmp) != unvisited.end())
                       { //tmp is in dictionary
                           State* newChild = new State(tmp);
                           front->child.push_back(newChild);
                           q[(count+1)%2].push(newChild);
                       }  
                   }
                } 
                garbage.push_back(front->s);
                if(q[count%2].empty())
                {
                    for(auto it:garbage)
                    {
                        unvisited.erase(it);
                    }
                    count++;
                    garbage.clear();
                }
            }
            vector<string> local;
            DFS(root, local, res, end);
            return res;
        }
    };

Log in to reply
 

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