Topics › Graphs › Problems on BFS/DFS

Word ladder I

Hard TUF ID 509 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given two words, beginWord and endWord, and a list wordList. A transformation sequence is a list beginWord -> s1 -> s2 -> ... -> sk in which every adjacent pair differs in exactly one letter, every si is in wordList, and sk == endWord. beginWord itself does not have to be in the list. Return the number of words in the shortest such sequence, or 0 if none exists.

Constraints: all words have the same length L with 1 ≤ L ≤ 10, lowercase letters only, 1 ≤ N ≤ 5000 words in the list, all distinct, and beginWord != endWord.

Example 1

beginWord = "hit", endWord = "cog"
wordList  = [hot, dot, dog, lot, log, cog]
answer    = 5        // hit -> hot -> dot -> dog -> cog

Example 2

beginWord = "hit", endWord = "cog"
wordList  = [hot, dot, dog, lot, log]
answer    = 0        // cog is not in the list, so it can never be reached

Modelling it as a graph. Make every word a vertex and join two words by an edge when they differ in exactly one letter. A transformation sequence is a path, and the shortest sequence is a shortest path. Every edge counts the same, so this is an unweighted shortest-path problem, and BFS solves it: BFS explores words in rounds, round k holding exactly the words whose shortest ladder has k words. The first round that contains endWord gives the answer.

The graph is never built explicitly. The only real question is how to find a word’s neighbours quickly, and that is where the approaches differ.

Approach 1: BFS comparing against every word

Intuition. To find the neighbours of a word, compare it with every word in the list and keep those that differ in exactly one position. A used flag per list entry stops a word from entering the queue twice. This is correct, but every dequeued word pays for a scan of the whole list.

Algorithm.

1. Put beginWord in the queue; steps = 1.
2. Process the queue one level at a time. For each word: if it equals endWord, return steps. Otherwise enqueue every unused list word that differs from it in exactly one letter, marking it used.
3. After each level, steps++. If the queue empties, return 0.

static int bruteForce(String beginWord, String endWord, List<String> wordList) {
    int n = wordList.size();
    boolean[] used = new boolean[n];
    Deque<String> q = new ArrayDeque<>();
    q.offer(beginWord);
    int steps = 1;                                   // words in the ladder so far
    while (!q.isEmpty()) {
        for (int size = q.size(); size > 0; size--) {
            String word = q.poll();
            if (word.equals(endWord)) return steps;
            for (int i = 0; i < n; i++) {
                if (!used[i] && differByOne(word, wordList.get(i))) {
                    used[i] = true;
                    q.offer(wordList.get(i));
                }
            }
        }
        steps++;
    }
    return 0;
}

static boolean differByOne(String a, String b) {
    if (a.length() != b.length()) return false;
    int diff = 0;
    for (int i = 0; i < a.length() && diff < 2; i++) {
        if (a.charAt(i) != b.charAt(i)) diff++;
    }
    return diff == 1;
}

Complexity. Time O(N^2 · L): up to N words are dequeued and each is compared with N words in O(L). Space O(N) for the queue and flags. With N = 5000 this is about 2.5 × 10^8 character comparisons, too slow for repeated tests.

Approach 2: Optimal, BFS generating neighbours letter by letter

Intuition. A word of length L has at most 25 · L possible one-letter variations, no matter how big the list is. With L ≤ 10 that is at most 250 candidates, far fewer than 5000 list words. So instead of searching the list, generate each candidate (replace position i with each letter a to z) and ask a hash set whether it is a real word.

The same set also serves as the visited marker. Removing a word from the set the moment it is enqueued guarantees it is never enqueued again, and that is safe because BFS reaches every word first along a shortest ladder. Any later route to it is at least as long, so nothing is lost.

Algorithm.

1. Put all list words in a set unvisited. If endWord is missing, return 0. Remove beginWord if present.
2. BFS level by level from beginWord, with steps = 1.
3. For each dequeued word: if it is endWord, return steps. Otherwise, for every position and every letter, build the candidate; if unvisited.remove(candidate) succeeds, enqueue it.
4. Return 0 if the queue empties.

static int optimal(String beginWord, String endWord, List<String> wordList) {
    Set<String> unvisited = new HashSet<>(wordList);
    if (!unvisited.contains(endWord)) return 0;
    unvisited.remove(beginWord);
    Deque<String> q = new ArrayDeque<>();
    q.offer(beginWord);
    int steps = 1;
    while (!q.isEmpty()) {
        for (int size = q.size(); size > 0; size--) {
            String word = q.poll();
            if (word.equals(endWord)) return steps;
            char[] w = word.toCharArray();
            for (int i = 0; i < w.length; i++) {
                char original = w[i];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    w[i] = ch;
                    String next = new String(w);
                    if (unvisited.remove(next)) q.offer(next);   // remove() doubles as "mark visited"
                }
                w[i] = original;
            }
        }
        steps++;
    }
    return 0;
}

Trying the original letter at a position is harmless: it rebuilds the current word, which is no longer in the set, so remove returns false.

Dry run on Example 1:

Complexity. Time O(N · L · 26 · L): each of up to N words generates 26 · L candidates, and building and hashing a candidate costs O(L). For N = 5000, L = 10 that is about 1.3 × 10^7 character operations. Space O(N · L) for the set and queue.

Approach 3: Bidirectional BFS

Intuition. A BFS that must go d levels deep, where each word has about b neighbours, touches roughly b^d words. Two searches, one from each end, that meet in the middle each go only d/2 deep, for about 2 · b^(d/2) words, which is dramatically smaller when d is large. At every round we expand the smaller of the two frontiers, which keeps the work balanced.

steps counts the words on the two partial ladders minus one. When a candidate generated from the front frontier is already in the back frontier, the two ladders join through that one edge, and the full ladder has steps + 1 words. Because both searches advance one whole level at a time, the first meeting happens at the smallest possible total length.

static int bidirectional(String beginWord, String endWord, List<String> wordList) {
    Set<String> dict = new HashSet<>(wordList);
    if (!dict.contains(endWord)) return 0;
    Set<String> front = new HashSet<>(List.of(beginWord)), back = new HashSet<>(List.of(endWord));
    dict.remove(beginWord);
    dict.remove(endWord);
    int steps = 1;                                   // words on both partial ladders, minus one
    while (!front.isEmpty() && !back.isEmpty()) {
        if (front.size() > back.size()) { Set<String> t = front; front = back; back = t; }
        Set<String> next = new HashSet<>();
        for (String word : front) {
            char[] w = word.toCharArray();
            for (int i = 0; i < w.length; i++) {
                char original = w[i];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    w[i] = ch;
                    String cand = new String(w);
                    if (back.contains(cand)) return steps + 1;   // the two searches meet
                    if (dict.remove(cand)) next.add(cand);
                }
                w[i] = original;
            }
        }
        front = next;
        steps++;
    }
    return 0;
}

Complexity. Same worst case as Approach 2, O(N · L^2 · 26), and O(N · L) space. In practice it visits a small fraction of the words. It is the version to mention when an interviewer asks how to speed up the BFS further.

Edge cases and pitfalls

• endWord not in the list. No ladder can end there. Approaches 2 and 3 return 0 immediately; Approach 1 just never finds it.
• beginWord inside the list. Remove it from the set first; otherwise one of its neighbours enqueues it again, which costs work and never helps.
• Count words, not edges. hit -> hot is a ladder of length 2. Starting steps at 1 keeps this right.
• Mark visited at enqueue time. Marking only on dequeue lets the same word sit in the queue many times and blows up the running time.
• Do not use DFS. DFS finds a path, not the shortest one, and exploring all paths is exponential.
• Words differing in two letters are not adjacent. hot -> dog needs a bridge word such as dot or hog.

Related problems

• Word ladder II asks for every shortest ladder, not just its length.
• Shortest path in undirected graph with unit weights is the same BFS on an explicit graph.
• Rotten Oranges is a level-by-level BFS on a grid.
• Distance of nearest cell having one uses BFS distances from many sources at once.