LeetCode----Word Ladder 2

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

1. Only one letter can be changed at a time
2. 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.

     分析：

     给定一个单词start, 问通过一系列变换是否能够得到单词end, 中间的单词都必须是给定的字典中的词。

     其实就是 从最初的一个状态，能够找到一个path, 到达最终的一个状态。

     Bingo! 图的搜索： 找到图中两个node之间的所有的最短路径。

     图的搜索有 深度优先（DFS） 和 广度优先（BFS）两种。

     BFS适用于解决寻找最短路径的问题，因此采用BFS

     
     

     class Solution {
     public:
         vector
           
            > findLadders(string start, string end, unordered_set
            
              &dict) { //BFS each node in graph has multipul fathers vector
             
               > result; vector
              
                path; bool found = false; unordered_set
               
                 visited; unordered_map
                
                  > father; queue
                 
                   current, next; if(start.size() != end.size()) return result; current.push(start); while(!current.empty()) { string str(current.front()); current.pop(); for(size_t i=0; i
                  
                    0 && !visited.count(new_str)){ visited.insert(new_str); next.push(new_str); father[new_str].push_back(str); } swap(c, new_str[i]); if(new_str == end){ found = true; break; } } }// end for if(current.empty() && !found) swap(current, next); }// end while buildPath(father, path, start, end, result); return result; } private: void buildPath(unordered_map
                   
                     > &father, vector
                    
                      &path, const string &start, const string &word, vector
                     
                       > &result){ path.push_back(word); if(word == start){ result.push_back(path); reverse(result.back().begin(), result.back().end()); } else{ for(auto f : father[word]) buildPath(father, path, start, f, result); } path.pop_back(); } };