Word Ladder
Given two words (beginWord and endWord), and a dictionary's word list, find the length of the shortest transformation sequence from beginWord to endWord, such that: 1) Only one letter can be changed at a time. 2) Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Constraints:
- 1 <= beginWord.length <= 10
- endWord.length == beginWord.length
- 1 <= wordList.length <= 5000
- wordList[i].length == beginWord.length
- beginWord, endWord, and wordList[i] consist of lowercase English letters.
- beginWord is not the same as endWord.
- All the words in wordList are unique.
Examples:
Input: ["hit","cog","dot","dog","lot","log","cog"], "hit", "cog"
Output: 5
Explanation: One possible transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", and another possible transformation is "hit" -> "hot" -> "lot" -> "log" -> "cog".
Solutions
Breadth-First Search
The solution uses a breadth-first search (BFS) approach to find the shortest transformation sequence. It starts with the beginWord and explores all possible transformations by changing one letter at a time. The transformed words are added to a queue and the process continues until the endWord is found or the queue is empty.
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> wordSet(wordList.begin(), wordList.end());
queue<string> q;
q.push(beginWord);
int length = 1;
while (!q.empty()) {
int size = q.size();
for (int i = 0;
i < size;
i++) {
string word = q.front();
q.pop();
if (word == endWord) return length;
for (int j = 0;
j < word.size();
j++) {
string nextWord = word;
for (char c = 'a';
c <= 'z';
c++) {
nextWord[j] = c;
if (wordSet.find(nextWord) != wordSet.end()) {
q.push(nextWord);
wordSet.erase(nextWord);
}
}
}
}
length++;
}
return 0;
}
}
;Follow-up:
What if the word list is very large and we need to optimize the solution for memory usage?
