How to do this without modifying the dictionary?


  • 0
    G
        I tried multiple approach like copying dictionary, aur keeping a visited map but everything gives a TLE. The only accepted solution I have is by modifying the dictionary. Can we do this without modifying the dictionary ?
        
            
        
    class Solution {
    public:
    
      //don't modify the dictionary
        int ladderLength(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); 
          
          
          unordered_set<string> visited;
         for ( auto it = dict.begin(); it != dict.end(); ++it )
            visited.insert(*it);
            
          while(!Q.empty())
          {
              P = Q.front(); 
              Q.pop();
              
              string curr = P.first;
              int level =  P.second;
              
              if(curr==end)
               return level;
               
             visited.erase(curr);
    
             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(visited.find(tmp) != visited.end())  //if the word is in dictionary and never visited 
                     {
                         pair<string, int> t = make_pair(tmp, level+1);
                         Q.push(t);
                     }
                 }
             }
          }
          return 0;
        }
    };

Log in to reply
 

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