2014.2.27 02:14
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.
Solution:
At first I tried to use Dijkstra's Algorithm on this problem, as I saw a graph in the words. But it proved to be unnecessary and inefficient.
Use BFS and queue instead and you'll make it.
One thing is very important: don't check if two words differ only by one letter, you should change one letter and see if it is still in the dictionary. This saves a lot of time.
Total time complexity is O(n^2). Space complexity is O(n). The constant factor is relatively large, so the algorithm is still expensive.
Accepted code:
1 // 7CE, 4RE, 4TLE, 1AC, BFS... 2 #include <queue> 3 #include <string> 4 #include <unordered_map> 5 #include <unordered_set> 6 using namespace std; 7 8 class Solution { 9 public: 10 int ladderLength(string start, string end, unordered_set<string> &dict) { 11 queue<pair<string, int> > qq; 12 string word, next_word; 13 unordered_map<string, int> um; 14 char ch, old_ch; 15 int result = 0; 16 bool suc = false; 17 pair<string, int> this_pair; 18 19 qq.push(make_pair(start, 1)); 20 um[start] = 1; 21 while (!qq.empty()) { 22 this_pair = qq.front(); 23 qq.pop(); 24 word = this_pair.first; 25 for (size_t i = 0; i < word.length(); ++i) { 26 old_ch = word[i]; 27 for (ch = 'a'; ch <= 'z'; ++ch) { 28 word[i] = ch; 29 if (word == end) { 30 suc = true; 31 result = this_pair.second + 1; 32 } 33 if (um.find(word) == um.end() && dict.find(word) != dict.end()) { 34 qq.push(make_pair(word, this_pair.second + 1)); 35 um[word] = this_pair.second + 1; 36 } 37 } 38 if (suc) { 39 break; 40 } 41 word[i] = old_ch; 42 } 43 if (suc) { 44 break; 45 } 46 } 47 while(!qq.empty()) { 48 qq.pop(); 49 } 50 return result; 51 } 52 };