Word Ladder II : Tried BFS and DFS but still getting TLE


  • 0
    G

    Hi All,

    First I used BFS to find the shortest length and I used that as parameter in DFS, so that I won't go beyond the shortest depth while exploring all the path. But still I am getting TLE for large test case and the reason I think is lots of path with depth d and I end up exploring all of them. Is there any way to optimize it further ?
    I tried going from start to end as well end to start but none of them works. Following is my code.

    class Solution {
    public:
    
       void DFS(string start, string end, unordered_set<string> &dict, vector<vector<string> > &ans, vector<string> tmp, int currDepth, int maxDepth)
      {
           if(currDepth>=maxDepth)
             return;
             
             
           if(start==end && (currDepth==(maxDepth-1)))
           {
               tmp.push_back(end);
               ans.push_back(tmp);
    
               return;
           }
           
           for(int i=0;i<start.size();i++)
           {
               string temp = start;
               for(char c='a'; c<='z'; c++)
               {
                   temp[i] = c;
                   if(dict.find(temp) != dict.end())
                   {
                       dict.erase(start);   //erase the word to avoid cycle
                       tmp.push_back(start);
                       DFS(temp, end, dict, ans, tmp, currDepth+1, maxDepth);
                       tmp.pop_back();
                       dict.insert(start);  //put it back for next iteration 
                   }
               }
           }
       }
    
        int BFS(string start, string end, unordered_set<string> &dict) {
          if(start==end || dict.size()==0)
           return 0;
           
          queue<pair<string, int> > Q;
          pair<string, int> P;
          P = make_pair(start, 1);
          Q.push(P);
          //wl.push(1); 
          
          while(!Q.empty())
          {
              P = Q.front(); 
              Q.pop();
              
              string curr = P.first;
              int level =  P.second;
              
              if(curr==end)
               return level;
               
             string tmp;  
             for(int i=0; i<curr.length(); i++)
             {
                 tmp = curr;
                 for(char c='a'; c<='z'; c++)  //try changing one character at a time
                 {
                     tmp[i] = c;
                     if(dict.find(tmp) != dict.end())  //if the word is in dictionary 
                     {
                         pair<string, int> t = make_pair(tmp, level+1);
                         Q.push(t);
                         dict.erase(tmp);
                     }
                 }
             }
          }
          return 0;
        }
        vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
            vector<vector<string> > ans;
            if(start ==end || dict.size()==0)
              return ans;
             
             unordered_set<string> dictCopy(dict);  
            //first find the shortest length
            //BFS is same word-ladder-i 
            int d = BFS(start, end, dict);
            if(!d)
              return ans;
             
            vector<string> tmp;
    
            DFS(end, start, dictCopy, ans, tmp, 0, d);
            return ans;
        }
    };
    

    Thanks in advance for your help.


  • 1
    R

    Here is how I use DFS and BFS to find all paths.

    class Solution {
    public:
        vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
            unordered_map<string,int> ladder;
            unordered_map<string,vector<string> > graph;
            queue<string> q;
            int min=std::numeric_limits<int>::max();
            
            ladder.insert(pair<string,int>(start,1));
            dict.insert(end);
            q.push(start);
            //BFS
            while(!q.empty()){
                string word=q.front();
                q.pop();
                
                if (word==end){
                    min=ladder[word];
                    continue;
                }
                
                int dis=ladder[word]+1;
                if (dis>min) break;
    
                for (int i=0;i<word.size();i++){
                    string temp=word;
                    for (char c='a';c<='z';c++){
                        temp[i]=c;
                        if (dict.find(temp)==dict.end()) continue;
                        
                        if (ladder.find(temp)==ladder.end()){
                            ladder.insert(pair<string,int>(temp,dis));
                            q.push(temp);
                            graph.insert(pair<string,vector<string> >(temp,vector<string>{word}));
                            continue;
                        }
                        
                        if (ladder[temp]<dis) continue;
                        else if (ladder[temp]==dis)
                            graph[temp].push_back(word);
                        
                    }
                }
            }
            vector<vector<string> > result;
            vector<string> builder;
            if (graph.find(end)==graph.end()) return result;
            buildResult(end,min-1,result,builder,graph);
            return result;
        }
    //DFS
    private:
        void buildResult(string end,int step,vector<vector<string> > &result, vector<string> &builder,unordered_map<string,vector<string> > &map){
            if (step==0){
                builder.push_back(end);
                result.push_back(vector<string>{builder.rbegin(),builder.rend()});
                builder.pop_back();
                return;
            }
            builder.push_back(end);
            for (string s:map[end])
                buildResult(s,step-1,result,builder,map);
            builder.pop_back();
        }
    };

  • 0
    G

    Could you please provide the summary what you are doing. Looking at your code seems to be very similar what I am doing. So what is the different thing you are doing here?


  • 0
    R

    It it very similar. Build a grpah which contains all the words in shortest paths. Then use dfs to backtrace all the paths.


  • 0
    C

    @gautamnitc, in reeclapple's code, he is using BFS to build the shortest paths graph, not just to determine the length of the shortest path. This step is important so that DFS is not wasting time following any paths that do not lead to the shortest paths.

    In your solution, your DFS is going down an entire path and backtracks when (currDepth >= maxDepth). Your DFS is already following many such paths and hence causing the TLE.


  • 1
    G

    Thanks got it


Log in to reply
 

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