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

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.

 

因为之前一直没自己写过Dijkstra算法，而且最开始感觉这题就是先转成图再用Dijkstra求最短路径，所以就一直没做，昨天复习了一下Dijkstra算法，打算把这题A掉，没想到居然爆内存了。

网上搜了下别人的代码，发现不用先转化成图，求边的时候直接枚举‘a’到‘z’就可以了，然后BFS。

1 class Solution { 2 public: 3     int ladderLength(string start, string end, unordered_set
     
       &dict) { 4         if (start.length() != end.length()) return 0; 5         if (start.empty() || end.empty()) return 0; 6         queue
      
        path; 7         path.push(start); 8         dict.erase(start); 9         int len = 1, cnt = 1;10         while (!dict.empty() && !path.empty()) {11             string cur = path.front();12             path.pop();13             --cnt;14             for (int i = 0; i < cur.size(); ++i) {15                 string tmp = cur;16                 for (char j = 'a'; j <= 'z'; ++j) {17                     if (tmp[i] == j) continue;18                     tmp[i] = j;19                     if (tmp == end) return len + 1;20                     if (dict.find(tmp) != dict.end()) {21                         path.push(tmp);22                         dict.erase(tmp);23                     }24                 }25             }26             if (cnt == 0) {27                 ++len;28                 cnt = path.size();29             }30         }31         return 0;32     }33 };
      
     

下面是Dijsktra算法，不过超内存了。

1 class Solution { 2 public: 3     bool match(const string &s1, const string &s2) { 4         if (s1.length() != s2.length()) return false; 5         int cnt = 0; 6         for (int i = 0; i < s1.length(); ++i) { 7             if (s1[i] != s2[i]) ++cnt; 8             if (cnt > 1) return false; 9         }10         return cnt == 1 ? true : false;11     }12     13     void buildGraph(vector
     
      
        > &graph, unordered_set
       
         &dict, string start, string end, int &start_idx, int &end_idx) {14         dict.insert(start);15         dict.insert(end);16         vector
        
          str_idx(dict.size());17         int idx = 0;18         for (auto i : dict) {19             str_idx[idx] = i;20             if (i == start) start_idx = idx;21             if (i == end) end_idx = idx;22             ++idx;23         }24         graph.assign(str_idx.size(), vector
         
          (str_idx.size(), INT_MAX));25         for (int i = 0; i < str_idx.size(); ++i) {26             for (int j = 0; j < str_idx.size(); ++j) {27                 if (match(str_idx[i], str_idx[j])) {28                     graph[i][j] = graph[j][i] = 1;29                 }30             }31         }32     }33     34     int dijkstra(vector
          
           
             > &graph, int start_idx, int end_idx) {35 int N = graph.size();36 vector
            
              s(N, false);37 vector
             
               dist(N, 0);38 int u = start_idx;39 for (int i = 0; i < N; ++i) {40 dist[i] = graph[start_idx][i];41 }42 dist[start_idx] = 0;43 s[start_idx] = true;44 for (int i = 0; i < N; ++i) {45 int tmp_max = INT_MAX;46 for (int j = 0; j < N; ++j) {47 if (!s[j] && tmp_max > dist[j]) {48 u = j;49 tmp_max = dist[j];50 }51 }52 s[u] = true;53 if (u == end_idx) return dist[u] + 1;54 for (int j = 0; j < N; ++j) {55 if (!s[j] && graph[u][j] < INT_MAX) {56 dist[j] = min(dist[j], dist[u] + graph[u][j]);57 }58 }59 }60 }61 62 int ladderLength(string start, string end, unordered_set
              
                &dict) {63 vector
               
                
                  > graph;64 int start_idx, end_idx;65 buildGraph(graph, dict, start, end, start_idx, end_idx);66 return dijkstra(graph, start_idx, end_idx);67 }68 };