Shortest Word Ladder Between Two Words
Solve this ProblemYou are given a start word, a target word and a list of allowed words. A ladder moves from one word to the next by changing exactly one letter, and every word after the start must come from the list. Find the number of words in the shortest ladder from start to target, or 0 if there is none.
Think of the words as nodes of a graph, with an edge between two words that differ in exactly one letter. Because each step costs the same, a breadth-first search returns the shortest ladder.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ words.length ≤ 12; every word (and start, target) has the same length between 1 and 5, all lowercase letters - ◆
start ≠ target; the words in the list are distinct; start may or may not be in the list - ◆
A ladder starts at start and ends at target; each next word must be in the list and differ from the previous word in exactly one letter - ◆
Return the number of words in the shortest ladder (including start and target), or 0 if the target is not in the list or cannot be reached
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Keep Relaxing Ladder Lengths Until Nothing Improves
BruteTreat the start and every list word as a node; two nodes are linked when they differ in exactly one letter. Give the start length 1 and everything else infinity, then sweep over all pairs again and again: if u is reachable and v is one letter away, offer dist[u] + 1 to v. Stop when a sweep changes nothing. Up to W sweeps of W² pairs (each comparison costs L) gives O(W³·L).
O(W³·L)O(W)1class Solution {
2 private boolean oneApart(String a, String b) {
3 int diff = 0;
4 for (int i = 0; i < a.length(); i++) {
5 if (a.charAt(i) != b.charAt(i)) diff++;
6 }
7 return diff == 1;
8 }
9
10 public int ladderLength(String start, String target, String[] words) {
11 int n = words.length;
12 String[] nodes = new String[n + 1];
13 for (int i = 0; i < n; i++) nodes[i] = words[i];
14 nodes[n] = start;
15 int INF = Integer.MAX_VALUE;
16 int[] dist = new int[n + 1];
17 Arrays.fill(dist, INF);
18 dist[n] = 1;
19 boolean changed = true;
20 while (changed) {
21 changed = false;
22 for (int u = 0; u <= n; u++) {
23 if (dist[u] == INF) continue;
24 for (int v = 0; v < n; v++) {
25 if (oneApart(nodes[u], nodes[v]) && dist[u] + 1 < dist[v]) {
26 dist[v] = dist[u] + 1;
27 changed = true;
28 }
29 }
30 }
31 }
32 int best = INF;
33 for (int i = 0; i < n; i++) {
34 if (words[i].equals(target)) best = Math.min(best, dist[i]);
35 }
36 return best == INF ? 0 : best;
37 }
38}Optimal — Breadth-First Search Over the Word Graph
OptimalEvery step has the same cost, so a breadth-first search from the start finds the shortest ladder. Keep the ladder length for each word (0 = not reached yet). Take a word from the queue; if it is the target, return its length. Otherwise every unreached list word that differs by exactly one letter gets length + 1 and joins the queue. Each word is queued once and compared with all W words: O(W²·L).
O(W²·L)O(W)1class Solution {
2 private boolean oneApart(String a, String b) {
3 int diff = 0;
4 for (int i = 0; i < a.length(); i++) {
5 if (a.charAt(i) != b.charAt(i)) diff++;
6 }
7 return diff == 1;
8 }
9
10 public int ladderLength(String start, String target, String[] words) {
11 int n = words.length;
12 String[] nodes = new String[n + 1];
13 for (int i = 0; i < n; i++) nodes[i] = words[i];
14 nodes[n] = start;
15 int[] dist = new int[n + 1];
16 dist[n] = 1;
17 Deque<Integer> queue = new ArrayDeque<>();
18 queue.add(n);
19 while (!queue.isEmpty()) {
20 int u = queue.poll();
21 if (nodes[u].equals(target)) return dist[u];
22 for (int v = 0; v < n; v++) {
23 if (dist[v] == 0 && oneApart(nodes[u], nodes[v])) {
24 dist[v] = dist[u] + 1;
25 queue.add(v);
26 }
27 }
28 }
29 return 0;
30 }
31}