word ladder

2023-11-04 01:48

文章标签 word ladder

本文主要是介绍word ladder，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：http://leetcode.com/onlinejudge#question_126

原题：

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

Note:

All words have the same length.
All words contain only lowercase alphabetic characters.

思路：

其实解题思路和Word Ladder完全一样，BFS，但是麻烦的是要返回所有的路径。

所以没办法，只能把每个单词所对应的前驱单词记录下来，当然有可能有多个，那么

就用一个vector<string>存储好，有这些记录就可以重构路径了。

代码：

[cpp]  view plain copy 
 class Solution {  
 public:  
     vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {  
         // Start typing your C/C++ solution below  
         // DO NOT write int main() function  
         pathes.clear();  
         dict.insert(start);  
         dict.insert(end);  
         vector<string> prev;  
         unordered_map<string, vector<string> > traces;  
         for (unordered_set<string>::const_iterator citr = dict.begin();   
                 citr != dict.end(); citr++) {  
             traces[*citr] = prev;  
         }  
           
         vector<unordered_set<string> > layers(2);  
         int cur = 0;  
         int pre = 1;  
         layers[cur].insert(start);  
         while (true) {  
             cur = !cur;  
             pre = !pre;  
             for (unordered_set<string>::const_iterator citr = layers[pre].begin();  
                     citr != layers[pre].end(); citr++)  
                 dict.erase(*citr);  
             layers[cur].clear();  
             for (unordered_set<string>::const_iterator citr = layers[pre].begin();  
                     citr != layers[pre].end(); citr++) {  
                 for (int n=0; n<(*citr).size(); n++) {    
                     string word = *citr;    
                     int stop = word[n] - 'a';    
                     for (int i=(stop+1)%26; i!=stop; i=(i+1)%26) {    
                         word[n] = 'a' + i;    
                         if (dict.find(word) != dict.end()) {    
                             traces[word].push_back(*citr);  
                             layers[cur].insert(word);   
                         }    
                     }  
                 }  
             }  
             if (layers[cur].size() == 0)  
                 return pathes;  
             if (layers[cur].count(end))  
                 break;  
         }  
         vector<string> path;  
         buildPath(traces, path, end);  
   
         return pathes;  
     }  
   
     private:  
         void buildPath(unordered_map<string, vector<string> > &traces,   
                 vector<string> &path, const string &word) {  
             if (traces[word].size() == 0) {  
                 path.push_back(word);  
                 vector<string> curPath = path;  
                 reverse(curPath.begin(), curPath.end());  
                 pathes.push_back(curPath);  
                 path.pop_back();  
                 return;  
             }  
   
             const vector<string> &prevs = traces[word];  
             path.push_back(word);  
             for (vector<string>::const_iterator citr = prevs.begin();  
                     citr != prevs.end(); citr++) {  
                 buildPath(traces, path, *citr);  
             }  
             path.pop_back();  
         }  
   
         vector<vector<string> > pathes;  
 };  