92.Word Ladder

HardGraphs · 13/19

Problem

A transformation sequence from beginWord to endWord is a list of words where each adjacent pair differs by exactly one letter, and every word after beginWord must appear in wordList.

Return the number of words in the shortest such sequence (including both beginWord and endWord), or 0 if no sequence exists. beginWord itself does not need to be in wordList.

Examples

Input:  beginWord = "hit", endWord = "cog",
        wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: hit -> hot -> dot -> dog -> cog has 5 words.

Input:  beginWord = "hit", endWord = "cog",
        wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: "cog" is not in the word list, so it can never be reached.

Constraints

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
All words consist of lowercase English letters; beginWord != endWord; words in wordList are unique.

💡 Key Insight

Treat every word as a node and connect two words if they differ by one letter. The question becomes shortest path in an unweighted graph, which is exactly what BFS answers. The only real design choice is how to find a word's neighbours quickly: comparing against all N words costs O(N · L), while trying all 26 · L single-letter substitutions and checking a hash set is far cheaper when N is large. Searching from both ends at once shrinks the explored frontier even further.

BFS Comparing All Words

TimeO(N² · L)SpaceO(N)

Intuition

Run BFS from beginWord, level by level. To expand a word, scan the whole word list and enqueue every unvisited word that differs in exactly one position. The first time we pop endWord, its level is the answer.

Algorithm

If endWord is not in wordList, return 0.
Queue beginWord with level = 1; keep a visited array over wordList.
For each level, pop every word; for each unvisited list word that differs by one letter: if it equals endWord return level + 1, else mark and enqueue it.
Increment level. If the queue empties, return 0.

Visualization

level 1: [hit]
level 2: [hot]           (hot differs from hit at index 1)
level 3: [dot, lot]
level 4: [dog, log]
level 5: cog found from dog -> return 5

Code

java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) {
            return 0;
        }
        int n = wordList.size();
        boolean[] visited = new boolean[n];
        Deque<String> queue = new ArrayDeque<>();
        queue.offer(beginWord);
        int level = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int s = 0; s < size; s++) {
                String word = queue.poll();
                for (int i = 0; i < n; i++) {
                    if (visited[i] || !oneApart(word, wordList.get(i))) {
                        continue;
                    }
                    if (wordList.get(i).equals(endWord)) {
                        return level + 1;
                    }
                    visited[i] = true;
                    queue.offer(wordList.get(i));
                }
            }
            level++;
        }
        return 0;
    }

    // true if a and b differ in exactly one position
    private boolean oneApart(String a, String b) {
        int diff = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i) && ++diff > 1) {
                return false;
            }
        }
        return diff == 1;
    }
}

Complexity

Time: O(N² · L) — each of the N words may be compared against all N words, each comparison O(L).
Space: O(N) — queue and visited array.

BFS with Letter Substitution

TimeO(N · L² · 26)SpaceO(N · L)

Intuition

Words are short (L <= 10) but the list can be long (N = 5000). Instead of scanning the list, generate every possible neighbour: replace each position with each of the 26 letters and check membership in a HashSet. Removing a word from the set when we enqueue it doubles as the visited marker.

Algorithm

Put wordList into a HashSet dict. If endWord is missing, return 0.
BFS from beginWord with level = 1.
For each popped word, for each index i and letter c: build the candidate; if it equals endWord return level + 1; if it is in dict, remove it and enqueue it.
After each level, level++. Return 0 if the queue empties.

Dry Run

flowchart LR
    A["hit<br/>level 1"] -->|"h_t: o"| B["hot<br/>level 2"]
    B -->|"_ot: d"| C["dot<br/>level 3"]
    B -->|"_ot: l"| D["lot<br/>level 3"]
    C -->|"do_: g"| E["dog<br/>level 4"]
    D -->|"lo_: g"| F["log<br/>level 4"]
    E -->|"_og: c"| G["cog<br/>level 5"]

Code

java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) {
            return 0;
        }
        Deque<String> queue = new ArrayDeque<>();
        queue.offer(beginWord);
        dict.remove(beginWord);
        int level = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int s = 0; s < size; s++) {
                char[] chars = queue.poll().toCharArray();
                for (int i = 0; i < chars.length; i++) {
                    char original = chars[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == original) {
                            continue;
                        }
                        chars[i] = c;
                        String next = new String(chars);
                        if (next.equals(endWord)) {
                            return level + 1;
                        }
                        if (dict.remove(next)) { // remove = mark visited
                            queue.offer(next);
                        }
                    }
                    chars[i] = original; // restore before the next position
                }
            }
            level++;
        }
        return 0;
    }
}

Complexity

Time: O(N · L² · 26) — each word is expanded once into 26 · L candidates, each costing O(L) to build and hash.
Space: O(N · L) — the dictionary and queue.

Bidirectional BFSOptimal

TimeO(N · L² · 26) worst case, but in practice far fewer words are expanded because each side only goes about half the depth.SpaceO(N · L)

Intuition

A BFS frontier grows roughly like b^d for branching factor b and depth d. Searching from both beginWord and endWord and meeting in the middle explores about 2 · b^(d/2) words instead. At every step we expand the smaller frontier; as soon as a generated word lies in the opposite frontier, the two searches have met.

Algorithm

Put wordList into dict; return 0 if endWord is missing.
front = {beginWord}, back = {endWord}, level = 1; remove endWord from dict.
While both sets are non-empty:
- If front.size() > back.size(), swap them.
- Build nextFront: for each word, each substitution next: if back contains next, return level + 1; if dict contains next, remove it and add to nextFront.
- front = nextFront, level++.
Return 0.

Visualization

front={hit}            back={cog}            level=1
expand front -> {hot}                        level=2
front={hot} (size 1) vs back={cog} (size 1): expand front -> {dot,lot}   level=3
swap: front={cog}, back={dot,lot}
expand {cog} -> dog, log are in dict -> {dog,log}                         level=4
front={dog,log} vs back={dot,lot}: expand dog -> "dot" is in back -> return 5

Code

java

import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) {
            return 0;
        }
        Set<String> front = new HashSet<>();
        Set<String> back = new HashSet<>();
        front.add(beginWord);
        back.add(endWord);
        dict.remove(beginWord);
        dict.remove(endWord);
        int level = 1;

        while (!front.isEmpty() && !back.isEmpty()) {
            if (front.size() > back.size()) { // always expand the smaller side
                Set<String> tmp = front;
                front = back;
                back = tmp;
            }
            Set<String> nextFront = new HashSet<>();
            for (String word : front) {
                char[] chars = word.toCharArray();
                for (int i = 0; i < chars.length; i++) {
                    char original = chars[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == original) {
                            continue;
                        }
                        chars[i] = c;
                        String next = new String(chars);
                        if (back.contains(next)) {
                            return level + 1; // the two searches met
                        }
                        if (dict.remove(next)) {
                            nextFront.add(next);
                        }
                    }
                    chars[i] = original;
                }
            }
            front = nextFront;
            level++;
        }
        return 0;
    }
}

Complexity

Time: O(N · L² · 26) worst case, but in practice far fewer words are expanded because each side only goes about half the depth.
Space: O(N · L) — dictionary and the two frontier sets.

Complexity Comparison

Approach	Time	Space
BFS Comparing All Words	O(N² · L)	O(N)
BFS with Letter Substitution	O(N · L² · 26)	O(N · L)
Bidirectional BFS	O(N · L² · 26), much smaller in practice	O(N · L)

Common Pitfalls

Returning the number of transformations instead of the number of words — the answer counts beginWord too.
Forgetting the early return 0 when endWord is not in wordList.
Marking words visited when they are popped instead of when they are enqueued, which lets the same word enter the queue many times.
Forgetting to restore chars[i] after trying all 26 letters at a position.
Using DFS — it finds a path, not the shortest one.