#127 Word Ladder

frequently reported atLinkedIn Amazon ByteDance / TikTok Apple Meta Microsoft

the problem

In plain words

Transform beginWord into endWord by changing one letter at a time; every intermediate word must be in wordList. Return the number of words in the shortest sequence (including both ends), or 0 if impossible.

in beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

out 5

hit → hot → dot → dog → cog.

in beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]

out 0

"cog" is not in the list.

1 ≤ word length ≤ 10
1 ≤ wordList.length ≤ 5000
Lowercase letters; all words the same length and unique; beginWord ≠ endWord

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBFS shortest path (unweighted)

Words are vertices; two words are adjacent if they differ in one letter. "Shortest sequence" in an unweighted graph = BFS. Generate neighbours by trying 26 letters per position instead of comparing all pairs.

solutions

From brute force to optimal

Compare every pair of words to create edges, then BFS.

For all i < j, connect words differing in exactly one position.
BFS from beginWord; dist counts words.

timeO(N² · L)

N² pairs, each compared in O(L).

spaceO(N²)

Up to N² edges in the adjacency lists.

javajava.util.*

1class Solution {2    /** Build the graph explicitly by comparing every pair of words, then BFS. */3    public int ladderLength(String beginWord, String endWord, List<String> wordList) {4        List<String> words = new ArrayList<>(wordList);5        if (!words.contains(endWord)) return 0;6        if (!words.contains(beginWord)) words.add(beginWord);7        int n = words.size();8        List<List<Integer>> adj = new ArrayList<>();9        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());10        for (int i = 0; i < n; i++)11            for (int j = i + 1; j < n; j++)12                if (oneApart(words.get(i), words.get(j))) {13                    adj.get(i).add(j);14                    adj.get(j).add(i);15                }16        int[] dist = new int[n]; // words in the sequence so far; 0 = unseen17        int start = words.indexOf(beginWord), target = words.indexOf(endWord);18        Deque<Integer> queue = new ArrayDeque<>(List.of(start));19        dist[start] = 1;20        while (!queue.isEmpty()) {21            int u = queue.poll();22            if (u == target) return dist[u];23            for (int v : adj.get(u))24                if (dist[v] == 0) {25                    dist[v] = dist[u] + 1;26                    queue.offer(v);27                }28        }29        return 0;30    }31 32    private boolean oneApart(String a, String b) {33        int diff = 0;34        for (int i = 0; i < a.length() && diff < 2; i++) if (a.charAt(i) != b.charAt(i)) diff++;35        return diff == 1;36    }37}

From each word, try every position × 26 letters; keep candidates still in the unvisited set.

unvisited = HashSet(wordList); return 0 if endWord is missing.
BFS level by level; length counts words.
For each word: for each position, for each letter → if in unvisited: endWord? return length+1; else remove and enqueue.

timeO(N · L² · 26)

Each of N words is expanded once: L positions × 26 letters, each building and hashing an L-char string.

spaceO(N · L)

The set and the queue store words of length L.

javajava.util.*

1class Solution {2    /** Don't build the graph: generate neighbours by trying all 26 letters at each position. */3    public int ladderLength(String beginWord, String endWord, List<String> wordList) {4        Set<String> unvisited = new HashSet<>(wordList);5        if (!unvisited.contains(endWord)) return 0;6        Deque<String> queue = new ArrayDeque<>(List.of(beginWord));7        unvisited.remove(beginWord);8        for (int length = 1; !queue.isEmpty(); length++) {9            for (int size = queue.size(); size > 0; size--) { // one level = one more word10                char[] w = queue.poll().toCharArray();11                for (int i = 0; i < w.length; i++) {12                    char original = w[i];13                    for (char ch = 'a'; ch <= 'z'; ch++) {14                        if (ch == original) continue;15                        w[i] = ch;16                        String next = new String(w);17                        if (!unvisited.contains(next)) continue;18                        if (next.equals(endWord)) return length + 1;19                        unvisited.remove(next); // removing = marking visited20                        queue.offer(next);21                    }22                    w[i] = original; // undo before trying the next position23                }24            }25        }26        return 0;27    }28}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    /** Don't build the graph: generate neighbours by trying all 26 letters at each position. */3    public int ladderLength(String beginWord, String endWord, List<String> wordList) {4        Set<String> unvisited = new HashSet<>(wordList);5        if (!unvisited.contains(endWord)) return 0;6        Deque<String> queue = new ArrayDeque<>(List.of(beginWord));7        unvisited.remove(beginWord);8        for (int length = 1; !queue.isEmpty(); length++) {9            for (int size = queue.size(); size > 0; size--) { // one level = one more word10                char[] w = queue.poll().toCharArray();11                for (int i = 0; i < w.length; i++) {12                    char original = w[i];13                    for (char ch = 'a'; ch <= 'z'; ch++) {14                        if (ch == original) continue;15                        w[i] = ch;16                        String next = new String(w);17                        if (!unvisited.contains(next)) continue;18                        if (next.equals(endWord)) return length + 1;19                        unvisited.remove(next); // removing = marking visited20                        queue.offer(next);21                    }22                    w[i] = original; // undo before trying the next position23                }24            }25        }26        return 0;27    }28}

Search from both ends and always expand the smaller frontier; stop when they meet.

front = {begin}, back = {end}.
Expand the smaller set by one level.
If a candidate is in the other set → the searches met.

timeO(N · L² · 26)

Same worst case, but each side only needs about half the depth — far fewer words explored in practice.

spaceO(N · L)

Two frontier sets and the dictionary.

javajava.util.*

1class Solution {2    /** Grow two frontiers (from begin and from end); always expand the smaller one. */3    public int ladderLength(String beginWord, String endWord, List<String> wordList) {4        Set<String> dict = new HashSet<>(wordList);5        if (!dict.contains(endWord)) return 0;6        Set<String> front = new HashSet<>(Set.of(beginWord)), back = new HashSet<>(Set.of(endWord));7        dict.remove(beginWord);8        dict.remove(endWord);9        for (int length = 2; !front.isEmpty() && !back.isEmpty(); length++) {10            if (front.size() > back.size()) { // expand the cheaper side11                Set<String> t = front;12                front = back;13                back = t;14            }15            Set<String> next = new HashSet<>();16            for (String word : front) {17                char[] w = word.toCharArray();18                for (int i = 0; i < w.length; i++) {19                    char original = w[i];20                    for (char ch = 'a'; ch <= 'z'; ch++) {21                        w[i] = ch;22                        String cand = new String(w);23                        if (back.contains(cand)) return length; // the two searches met24                        if (dict.remove(cand)) next.add(cand);25                    }26                    w[i] = original;27                }28            }29            front = next;30        }31        return 0;32    }33}

in the room

How to say it in the interview

talk track

Say: "It's shortest path in an unweighted implicit graph → BFS."
Point out the cost trade-off: comparing pairs is N²·L; generating 26·L candidates per word wins when N is large.
Removing a word from the set when you enqueue it is the visited mark.

traps

Returning edges instead of words (off by one).
Not checking that endWord is in the list first.
Forgetting to restore w[i] before trying the next position.

what they ask next

Follow-ups

Word Ladder II (LC 126): return all shortest sequences?

BFS to record each word's parents level by level (only from the previous level), then DFS/backtrack from endWord to rebuild paths.

before you submit

Edge cases to test

endWord not in wordList → 0 straight away.
beginWord need not be in the list; if it is, remove it so it isn't revisited.
endWord is one change away → 2 (the answer counts words, not changes).
No ladder exists → the queue empties and the answer is 0.

practise next