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.
import java.util.*;
public
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
int length = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0;
i < size;
i++) {
String word = queue.poll();
if (word.equals(endWord)) return length;
for (int j = 0;
j < word.length();
j++) {
for (char c = 'a';
c <= 'z';
c++) {
String nextWord = word.substring(0, j) + c + word.substring(j + 1);
if (wordSet.contains(nextWord)) {
queue.offer(nextWord);
wordSet.remove(nextWord);
}
}
}
}
length++;
}
return 0;
}
}Follow-up:
What if the word list is very large and we need to optimize the solution for memory usage?
