Given a begin_word and end_word, find the words that transforms from begin_word to end_word.
Example 1: Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.
This question can be solved in 2 ways.
- BFS
- 2 end BFS
-
Solving using regular BFS:
So the question gives us starting word and ending word, and a word dictionary. The goal here is to see if there is a way from starting word to ending word by changing only one letter at a time.
One simple way is the brute force method, that traverses all the cases.
If we consider our example, the starting word is “hit”, we start by replacing from the starting letter “ait” “bit” “cit” … “yit” “zit”, if any word is present in the dictionary, then save that word. When we reach “hot”, we save it, then again start with the first character “cot” “dot”, now “dot” is also present, save it.
Hence we use BFS instead of DFS, because, BFS ensures the shortest path.
-
Solving using 2 end BFS.
In this solution we start the path simultaneously from the start word and end word and merge in middle.
#include<iostream> #include<vector> #include<string> #include<unordered_map> #include<unordered_set> #include<queue> using namespace std; int ladderLength_bfs(string beginWord, string endWord, vector<string>& wordList) { unordered_set<string> wordSet(wordList.begin(), wordList.end()); unordered_map<string, int> pathCnt{{{beginWord, 1}}}; queue<string> q{{beginWord}}; while (!q.empty()) { string word = q.front(); q.pop(); for (int i = 0; i < word.size(); ++i) { string newWord = word; for (char ch = 'a'; ch <= 'z'; ++ch) { newWord[i] = ch; if (wordSet.count(newWord) && newWord == endWord) return pathCnt[word] + 1; if (wordSet.count(newWord) && !pathCnt.count(newWord)) { q.push(newWord); pathCnt[newWord] = pathCnt[word] + 1; } } } } return 0; } int ladderLength_two_end_bfs(string beginWord, string endWord, vector<string>& wordList) { unordered_set<string> dict(wordList.begin(), wordList.end()); if (dict.count(endWord) == 0) return 0; unordered_set<string> string1 = {beginWord}; unordered_set<string> string2 = {endWord}; dict.erase(endWord); int step = 0; while (!string1.empty() && !string2.empty()) { step++; if (string1.size() > string2.size()) swap(string1, string2); unordered_set<string> temp; for (auto word : string1) { for (int i=0; i<word.size(); i++) { char oldChar = word[i]; for (char c='a'; c<='z'; c++) { if (c == oldChar) continue; string newWord = word; newWord[i] = c; if (string2.count(newWord)) return step+1; if (dict.count(newWord)) { temp.insert(newWord); dict.erase(newWord); } } } } swap(string1, temp); } return 0; } int main() { vector<string> wordList; wordList.push_back("hot"); wordList.push_back("dot"); wordList.push_back("dog"); wordList.push_back("lot"); wordList.push_back("log"); wordList.push_back("cog"); string beginWord = "hit"; string endWord = "cog"; cout << "Length of shortest chain using one end BFS is: "<< ladderLength_bfs(beginWord, endWord, wordList)<<endl; cout << "Length of shortest chain using two end BFS is: "<< ladderLength_two_end_bfs(beginWord, endWord, wordList)<<endl; return 0; }
Output:
Length of shortest chain using one end BFS is: 5 Length of shortest chain using two end BFS is: 5
Raghav
I think this can be solved using graphs.
Make the initial string as the source and final as destination. If there exists a word in the list such it is just one character away from the initial string, then add this string as the neighbor. Repeat the same for all the strings in the list.
Now find if there is a path from the source to the destination and report the shortest one. (Dijikstra possibly)