Word Ladder
Problem Statement
Given a beginWord, an endWord, and a list of words (wordList), find the length of the shortest transformation sequence from beginWord to endWord where:
- Only one letter can be changed at a time.
- Each transformed word must exist in the wordList.
Return 0 if no transformation is possible.
Example:
- Input:
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] - Output:
5(hit → hot → dot → dog → cog)
Noob-Friendly Explanation
Imagine a word game: starting from one word, you can change exactly ONE letter at a time, and each new word must be a real word from a dictionary. You want to reach the target word in the fewest steps possible.
Think of every word as a node in a graph. Two words are connected if they differ by exactly one letter. Now the problem becomes: find the shortest path from the start word to the end word. BFS is perfect for this!
Approach 1: Brute Force (BFS with Word Comparison)
Intuition
Use BFS. For each word in the queue, compare it with every word in the list to find words that differ by exactly one letter. This comparison is O(M) per pair where M is word length.
Algorithm
- Add beginWord to queue with level 1.
- Use a set for quick lookups.
- For each word, compare with all words in the list.
- If a word differs by one letter and hasn't been used, add to queue.
- If we reach endWord, return the level.
import java.util.*;
public class WordLadderBruteForce {
public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
if (!wordSet.contains(endWord)) return 0;
Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.add(beginWord);
visited.add(beginWord);
int level = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String word = queue.poll();
if (word.equals(endWord)) return level;
// Compare with every word in the set
Iterator<String> it = wordSet.iterator();
while (it.hasNext()) {
String candidate = it.next();
if (!visited.contains(candidate) && differsByOne(word, candidate)) {
visited.add(candidate);
queue.add(candidate);
}
}
}
level++;
}
return 0;
}
static boolean differsByOne(String a, String b) {
if (a.length() != b.length()) return false;
int diff = 0;
for (int i = 0; i < a.length(); i++) {
if (a.charAt(i) != b.charAt(i)) diff++;
if (diff > 1) return false;
}
return diff == 1;
}
public static void main(String[] args) {
List<String> wordList = Arrays.asList("hot","dot","dog","lot","log","cog");
System.out.println(ladderLength("hit", "cog", wordList)); // 5
}
}Complexity Analysis
- Time Complexity: O(N * M * 26) in the worst case, but comparing with all N words at each step makes it O(N^2 * M).
- Space Complexity: O(N * M) — for the visited set and queue.
Approach 2: Optimal (BFS with Character Replacement)
Intuition
Instead of comparing with every word, for each position in the current word, try replacing with each of the 26 letters. Check if the resulting word exists in the word set. This reduces comparisons significantly when the word list is large.
Algorithm
- Put all words in a HashSet.
- BFS from beginWord.
- For each word, try changing each character to every letter a-z.
- If the new word is in the set, add to queue and remove from set (to avoid revisiting).
- Return the level when endWord is found.
import java.util.*;
public class WordLadderOptimal {
public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
if (!wordSet.contains(endWord)) return 0;
Queue<String> queue = new LinkedList<>();
queue.add(beginWord);
wordSet.remove(beginWord);
int level = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String word = queue.poll();
if (word.equals(endWord)) return level;
char[] chars = word.toCharArray();
for (int j = 0; j < chars.length; j++) {
char original = chars[j];
for (char c = 'a'; c <= 'z'; c++) {
if (c == original) continue;
chars[j] = c;
String newWord = new String(chars);
if (wordSet.contains(newWord)) {
queue.add(newWord);
wordSet.remove(newWord); // mark as visited
}
}
chars[j] = original; // restore
}
}
level++;
}
return 0;
}
public static void main(String[] args) {
List<String> wordList = Arrays.asList("hot","dot","dog","lot","log","cog");
System.out.println(ladderLength("hit", "cog", wordList)); // 5
}
}Complexity Analysis
- Time Complexity: O(N × M × 26) — for each word (N), we try each position (M) with 26 characters.
- Space Complexity: O(N × M) — for the set and queue storing words.