Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence 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"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters

思路：

这道题的思路应该是图和BFS。

最开始写错了，写成了图和DFS，导致总是超时。后来修改的时候增加了记录中间结果以及剪枝，但还总是超时。代码如下：

 1     map<string, vector<string> > table;
 2     map<string, bool> visit;
 3     map<string, int> result;
 4     int minAll;
 5     void initializeTable(string s, unordered_set<string>  &dict){
 6         int l = s.length();
 7         int i,n;
 8         for(unordered_set<string>::iterator it = dict.begin(); it != dict.end(); it++){
 9             n = 0;
10             string t = *it;
11             for(i = 0; i < l; i++){
12                 if(s[i] != t[i])
13                     n++;
14                 if(n>1)
15                     break;
16             }
17             if(n == 1)
18                 table[s].push_back(t);
19         }
20     }
21     int minLength(string start, string end, int step){
22         if(start == end)
23             return 1;
24         if(table.find(start) == table.end())
25             return 99999;
26         if(result.find(start) != result.end())
27             return result[start];
28         if(step >= minAll)
29             return 99999;
30         vector<string> next = table[start];
31         visit[start] = true;
32         int curMin = 99999;
33         for(int i = 0; i < next.size(); i++){
34             if(visit[next[i]])
35                 continue;
36             int t = 1 + minLength(next[i], end, step+1);
37             if(t < curMin)
38                 curMin = t;
39         }
40         visit[start] = false;
41         result[start] = curMin;
42         if(minAll > step+curMin)
43             minAll = step+curMin;
44         return curMin;
45     }
46     int ladderLength(string start, string end, unordered_set<string> &dict) {
47         // IMPORTANT: Please reset any member data you declared, as
48         // the same Solution instance will be reused for each test case.
49         table.clear();
50         initializeTable(start, dict);
51         initializeTable(end, dict);
52         dict.insert(end);
53         minAll = INT_MAX;
54         for(unordered_set<string>::iterator it = dict.begin(); it != dict.end(); it++){
55             initializeTable(*it, dict);
56             visit[*it] = false;
57         }
58         return minLength(start, end, 1);
59     }

看了网上的一些分析，改成BFS，并且在最开始没有必要建图，那样复杂度是O（n^2）。因为每个单词每次只改变一个字母，所以可以对每个单词的每个字母进行修改，复杂度是O（26*lengthOfWord）。修改后的代码如下：

 1     int ladderLength(string start, string end, unordered_set<string> &dict) {
 2         // IMPORTANT: Please reset any member data you declared, as
 3         // the same Solution instance will be reused for each test case.
 4         dict.insert(end);
 5         queue<pair<string, int> > q;
 6         q.push(pair<string, int>(start, 1));
 7         int result = 0;
 8         while(!q.empty()){
 9             string tmp = q.front().first;
10             int step = q.front().second;
11             if(tmp == end){
12                 result = step;
13                 break;
14             }
15             q.pop();
16             for(int i = 0; i < tmp.length(); i++){
17                 char tc = tmp[i];
18                 for(char c = 'a'; c <= 'z'; c++){
19                     if(tc == c)
20                         continue;
21                     tmp[i] = c;
22                     if(dict.find(tmp) != dict.end()){
23                         q.push(pair<string, int>(tmp, step+1));
24                         dict.erase(tmp);
25                     }
26                     tmp[i] = tc;
27                 }
28             }
29         }
30         return result;
31     }