5/26/2014

Leetcode - Word Ladder

 class Solution {  
 public:  
   int ladderLength(string start, string end, unordered_set<string> &dict) {  
     // BFS  
     queue<string> q;  
     q.push(start);  
     dict.erase(start);  
     int length = 1;  
     while(!q.empty()) {  
       queue<string> tempQ;  
       while(!q.empty()) {  
         string str(q.front());  
         q.pop();  
         set<string> ret(getOneEditedWord(str, dict));  
         for(string s : ret) {  
           if(s == end) {  
             return length + 1;  
           }  
           tempQ.push(s);  
         }  
       }  
       length++;  
       swap(q, tempQ);  
     }  
       return 0;  
     }  
   set<string> getOneEditedWord(string str, unordered_set<string> & dict) {  
     set<string> result;  
     for(int i = 0; i < str.length(); ++i) {  
       for(int j = 'a'; j <='z'; ++j) {  
         if(j == str[i]) {  
           continue;  
         }  
         char temp = str[i];  
         str[i] = j;  
         if(dict.count(str) > 0) {  
           result.insert(str);  
           dict.erase(str);  
         }  
         str[i] = temp;  
       }  
     }  
     return result;  
   }  
 };  

No comments: