Back to DSA
Word Ladder
hardStarting from a given word, transform it into a target word by changing one letter at a time. Every intermediate word must exist in a provided dictionary. Find the length of the shortest such transformation chain (counting both endpoints). Return 0 if no chain exists.
Examples
Example 1:
Input:
beginWord = "cat", endWord = "dog", wordList = ["cot","dot","dog","cog","dat"]Output:
4Explanation: cat -> cot -> cog -> dog (4 words).
Example 2:
Input:
beginWord = "run", endWord = "fly", wordList = ["fun","fin","fry"]Output:
0Explanation: The end word 'fly' is not in the dictionary.
Hints
import java.util.*;
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> words = new HashSet<>(wordList);
if (!words.contains(endWord)) return 0;
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
int steps = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
char[] curr = queue.poll().toCharArray();
for (int j = 0; j < curr.length; j++) {
char orig = curr[j];
for (char c = 'a'; c <= 'z'; c++) {
curr[j] = c;
String next = new String(curr);
if (next.equals(endWord)) return steps + 1;
if (words.contains(next)) {
words.remove(next);
queue.offer(next);
}
}
curr[j] = orig;
}
}
steps++;
}
return 0;
}
}Time complexity
O(M^2 * N)Space complexity
O(M * N)