【leetcode】Word Ladder II

Word Ladder II

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.

先使用BFS，得到father，记录广度搜索路径上，每一个节点的父节点（可以有多个）

因此采用 unordered_map<string,unordered_set<string>> 数据结构

例如father["aaa"]=["baa","caa"]表示了aaa在广度优先搜素路径上的父节点为"baa","caa";

广度优先搜索时，从start开始，

找到与start相邻的节点 node1,node2,.....;

并记录每一个节点的父节点为start

然后从node1，node2...开始，遍历下一层

直到找到end节点停止（注意，必须上一层节点全部遍历完

找到father 路径后，从end开始往前dfs就可以得到所有的结果了

 1 class Solution {
 2 public:
 3     vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
 4        
 5         vector<vector<string>> result;
 6         unordered_set<string> unvisited=dict;
 7        
 8         dict.insert(start);
 9         dict.insert(end);
10        
11         unordered_map<string,unordered_set<string>> father;
12         if(unvisited.count(start)==0) unvisited.erase(start);
13        
14        
15         unordered_set<string> curString,nextString;
16         curString.insert(start);
17        
18        
19         while(curString.count(end)==0&&curString.size()>0)
20         {
21            
22             for(auto it=curString.begin();it!=curString.end();it++)
23             {
24                 string word=*it;
25                 for(int i=0;i<word.length();i++)
26                 {
27                     string tmp=word;
28                     for(int j='a';j<='z';j++)
29                     {
30                         if(tmp[i]==j) continue;
31                         tmp[i]=j;
32                         if(unvisited.count(tmp)>0)
33                         {
34                             nextString.insert(tmp);
35                             father[tmp].insert(word);
36  
37                         }
38                        
39                     }
40                 }
41             }
42            
43             if(nextString.size()==0) break;
44            
45             for(auto it=nextString.begin();it!=nextString.end();it++)
46             {
47                 //必须遍历完了curString中所有的元素，才能在unvisited中删除（因为可能有多个父节点对应着该节点）
48                 unvisited.erase(*it);
49             }
50            
51             curString=nextString;
52             nextString.clear();
53            
54         }
55        
56         if(curString.count(end)>0)
57         {
58             vector<string> tmp;
59             dfs(father,end,start,result,tmp);
60         }
61        
62         return result;
63     }
64    
65    
66     void dfs(unordered_map<string,unordered_set<string>> &father,string end,string start,vector<vector<string>> &result,vector<string> tmp)
67     {
68         tmp.push_back(end);
69         if(end==start)
70         {
71             reverse(tmp.begin(),tmp.end());
72             result.push_back(tmp);
73             return;
74         }
75        
76         for(auto it=father[end].begin();it!=father[end].end();it++)
77         {
78             dfs(father,*it,start,result,tmp);
79         }
80     }
81 };