Word Ladder

HardBFS · Implicit Graph🧩 Graph BFS LeetCode #127 ↗Updated Oct 30, 2026

Problem

Turn beginWord into endWord changing one letter per step; every word after the first must be in wordList. Return the word count of the shortest such chain (both ends included), or 0 if none.

Inputhit → cog, [hot,dot,dog,lot,log,cog]Output5

Inputhit → cog, [hot,dot,dog,lot,log]Output0

word length M ≤ 10 · N = |wordList| ≤ 5000 · lowercase, unique · begin ≠ end

Try it yourself

Java

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Words are nodes, one-letter changes are edges of an unweighted graph ⇒ BFS. Generate neighbours by trying 26 letters per position, not by scanning the list.

PatternGraph BFS

Instinct Minimum moves, fewest steps or shortest transformation where every step costs the same: spread outward level by level with a queue.

Memory hack Ripples in a pond: every ring is one step farther, so the first ring that touches the target is the answer.

Open the Graph BFS guide →

Approaches

Brute ForceBFS, Compare with Every Word

Time O(N²·M)Space O(N)

Plain level-order BFS; neighbours are found by scanning the whole list for unused words differing in exactly one position — O(N·M) per dequeued word.

Java

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    boolean[] used = new boolean[wordList.size()];
    Queue<String> queue = new LinkedList<>(List.of(beginWord));
    for (int level = 1; !queue.isEmpty(); level++) {
        for (int size = queue.size(); size > 0; size--) {
            String cur = queue.poll();
            if (cur.equals(endWord)) return level;
            for (int i = 0; i < wordList.size(); i++) {
                String w = wordList.get(i);
                int diff = 0;
                for (int k = 0; k < w.length(); k++) if (w.charAt(k) != cur.charAt(k)) diff++;
                if (!used[i] && diff == 1) { used[i] = true; queue.offer(w); }
            }
        }
    }
    return 0;
}

Correct shortest path, but the neighbour scan is quadratic in N.

BetterBFS with Letter Substitution

Time O(N·26·M²)Space O(N·M)

Put the words in a HashSet. For a word, try every position × every letter (26·M candidates, each built and hashed in O(M)). words.remove(next) both checks membership and marks it visited.

Java

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<>(List.of(beginWord));
    words.remove(beginWord);
    for (int level = 1; !queue.isEmpty(); level++) {
        for (int size = queue.size(); size > 0; size--) {
            char[] chars = queue.poll().toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char orig = chars[i];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    chars[i] = ch;
                    String next = new String(chars);
                    if (next.equals(endWord)) return level + 1;
                    if (words.remove(next)) queue.offer(next); // visit once
                }
                chars[i] = orig;
            }
        }
    }
    return 0;
}

Neighbour generation no longer depends on N — the standard accepted solution.

OptimalBidirectional BFS

Time O(N·26·M²)Space O(N·M)

Grow one frontier from beginWord and one from endWord, always expanding the smaller one. They meet in the middle, so with branching factor b and depth d we visit about 2·b^d/2 words instead of b^d.

Java

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> words = new HashSet<>(wordList);
    if (!words.contains(endWord)) return 0;
    Set<String> front = new HashSet<>(List.of(beginWord));
    Set<String> back = new HashSet<>(List.of(endWord));
    words.removeAll(List.of(beginWord, endWord));
    for (int level = 1; !front.isEmpty() && !back.isEmpty(); level++) {
        if (front.size() > back.size()) { Set<String> t = front; front = back; back = t; }
        Set<String> next = new HashSet<>();
        for (String w : front) {
            char[] chars = w.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char orig = chars[i];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    chars[i] = ch;
                    String cand = new String(chars);
                    if (back.contains(cand)) return level + 1; // frontiers meet
                    if (words.remove(cand)) next.add(cand);
                }
                chars[i] = orig;
            }
        }
        front = next;
    }
    return 0;
}

Same worst-case bound, but explores far fewer words in practice.

At a glance

Level	Approach	Time	Space
Brute Force	BFS, Compare with Every Word	`O(N²·M)`	`O(N)`
Better	BFS with Letter Substitution	`O(N·26·M²)`	`O(N·M)`
Optimal	Bidirectional BFS	`O(N·26·M²)`	`O(N·M)`

Common pitfalls

Counting edges, not words — count both ends.
Marking visited on dequeue — duplicate queueing.
No early exit when endWord ∉ list.

Interview tips

“Shortest” + unweighted graph ⇒ BFS; say it up front.
Compare neighbour costs: N·M scan vs 26·M generation.
Offer bidirectional BFS as the follow-up for long ladders.

Pattern

BFS on an implicit graph → minimum number of single-step transformations between states.

My notes saved in this browser