Q25: How do you solve Word Ladder (Shortest Transformation Sequence) using BFS?
Find the shortest transformation path from beginWord to endWord changing one letter at a time where intermediate words exist in wordList. Model as an unweighted graph where edges connect words differing by 1 character. Execute BFS starting at beginWord to guarantee finding the shortest path length.
BFS Word Ladder Solution
import java.util.*;
public class WordLadder {
public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>(wordList);
if (!set.contains(endWord)) return 0;
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
int level = 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 original = curr[j];
for (char c = 'a'; c <= 'z'; c++) {
if (curr[j] == c) continue;
curr[j] = c;
String next = new String(curr);
if (next.equals(endWord)) return level + 1;
if (set.contains(next)) {
queue.offer(next);
set.remove(next); // Mark visited
}
}
curr[j] = original;
}
}
level++;
}
return 0;
}
}💡 Generates character mutations and traverses transformation steps using BFS level by level.
Key Takeaways
- BFS finds the shortest path in unweighted graphs.
- Generate one-letter mutations dynamically to find adjacent valid dictionary words.
Knowledge Check
Why is Breadth-First Search (BFS) preferred over Depth-First Search (DFS) for Word Ladder?