SyntaxPilot
Courses/DSA and Coding Problems/Lesson 57
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 57 of 90

Word ladder (hard)

queued

These are the notes for DSA episode 57. So far every graph was handed to us as a list of edges. Today the graph is hidden in the rules: words are nodes, and two words are joined when they differ in exactly one letter. We start from a real-life puzzle (Lewis Carroll's word ladders), define every word, try the obvious idea (depth-first search over every path: correct, but Time Limit Exceeded on just 125 three-letter words), see why it explodes, and find the key insight: fewest steps on equal-cost edges = breadth-first search (BFS), with neighbours made on demand by changing each letter a..z and checking a HashSet. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real.

The problem, in real life

In 1879 Lewis Carroll, the author of Alice in Wonderland, published a word puzzle in a magazine: turn one word into another by changing one letter at a time, and every step must be a real word.

COLD → CORD → CARD → WARD → WARM: five words.

The challenge is to use as few words as possible. Spell-checkers ("did you mean…?"), word games and DNA-mutation searches all do this kind of search.

In the puzzle In code
A real word a node, a string in wordList
Change one letter an edge between two strings that differ in exactly one position
The dictionary a HashSet<String> (instant "is this a word?")
Fewest words from start to goal shortest path in an unweighted graph: BFS

Every word, from zero

  • Transformation sequence (word ladder): beginWord → s1 → s2 → … → endWord, where each neighbouring pair differs by exactly one letter and every si is in wordList. beginWord does not need to be in the list.
  • Graph, node, edge: a node is a thing (here a word); an edge joins two related nodes (here, one letter apart).
  • Unweighted graph: every edge costs the same (one step).
  • Implicit graph: a graph that is never stored as a list of edges; we generate a node's neighbours only when we need them, from a rule.
  • Depth-first search (DFS): go as deep as possible down one path, then back up (backtrack) and try the next. Finds a path, not the shortest one.
  • Backtracking: undoing the last choice (used.remove(next)) so another path can use that word.
  • Breadth-first search (BFS): visit everything 1 step away, then 2 steps, then 3, using a queue. In an unweighted graph, the first time BFS reaches a node is along a shortest path (episode 47).
  • Level (ring): all nodes at the same distance from the start.
  • Queue (ArrayDeque): first in, first out.
  • HashSet: a set with O(1) average contains, add and remove (episode 46).
  • Visited: a node already queued; we never queue it again. Here, "removed from the set" means visited.
  • Bidirectional BFS: BFS from both ends at once, stopping when they meet.

Problem statement

LeetCode 127, Word Ladder. Given beginWord, endWord and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if none exists.

beginWord endWord wordList Answer
hit cog [hot, dot, dog, lot, log, cog] 5 (hit → hot → dot → dog → cog)
hit cog [hot, dot, dog, lot, log] 0 (cog isn't in the list)

Constraints: 1 ≤ beginWord.length ≤ 10, all words have the same length, 1 ≤ wordList.length ≤ 5000, lowercase letters, beginWord != endWord, words in wordList are unique.

Obvious idea: walk every path, keep the shortest

From the current word, try every list word that is one letter apart; a used set stops us walking in circles; when we reach endWord, remember the length; then backtrack and try other paths.

import java.util.*;

public class Main {
    static int best;
    static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        best = Integer.MAX_VALUE;
        Set<String> used = new HashSet<>();
        used.add(beginWord);
        dfs(beginWord, endWord, wordList, used, 1);
        return best == Integer.MAX_VALUE ? 0 : best;
    }
    static void dfs(String w, String end, List<String> list, Set<String> used, int len) {
        if (w.equals(end)) { best = Math.min(best, len); return; }
        for (String next : list)
            if (!used.contains(next) && oneApart(w, next)) {
                used.add(next);
                dfs(next, end, list, used, len + 1);
                used.remove(next);
            }
    }
    static 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++;
        return diff == 1;
    }
    public static void main(String[] args) {
        List<String> a = List.of("hot", "dot", "dog", "lot", "log", "cog");
        List<String> b = List.of("hot", "dot", "dog", "lot", "log");
        System.out.println(ladderLength("hit", "cog", a));
        System.out.println(ladderLength("hit", "cog", b));
    }
}
5
0

Correct. Now every three-letter word made of the letters a to e (just 125 words), from aaa to eee:

        List<String> list = new ArrayList<>();
        for (char x = 'a'; x <= 'e'; x++)
            for (char y = 'a'; y <= 'e'; y++)
                for (char z = 'a'; z <= 'e'; z++) list.add("" + x + y + z);
        long t0 = System.nanoTime();
        int words = ladderLength("aaa", "eee", list);
        System.out.println(words + " words, " + (System.nanoTime() - t0) / 1000000 + " ms");

Result in the SyntaxPilot compiler: Time Limit Exceeded (no output after 25 seconds). The answer is only 4 words (aaa → eaa → eea → eee), but DFS must try every path to be sure no shorter one exists.

Why every path explodes

  • Every word here has 12 neighbours (3 positions × 4 other letters).
  • The number of paths grows like 12^length: paths of length 10 ≈ 12^10 ≈ 6,000 crore.
  • DFS goes deep first, so the first path it finds is usually long. It can never stop early, because a shorter path might still be waiting in another branch.

We need a search that finds the shortest path first.

The key insight: a hidden graph, searched level by level

  1. Words are nodes; one letter apart is an edge. Example 1:
            dot ── dog
           / |      |  \
hit ── hot   |      |   cog
           \ |      |  /
            lot ── log
  1. Every edge is one step, so this is an unweighted graph, and BFS finds the fewest steps. It explores in rings:
Level Words Ladder length so far
1 hit 1
2 hot 2
3 dot, lot 3
4 dog, log 4
5 cog (found: stop) 5
  1. Neighbours on demand. Comparing a word with all N words costs O(N · L) per word, O(N² · L) in total. Instead, change each of the L letters to each of a..z: only 26 · L candidates (260 for a 10-letter word), each checked in a HashSet in O(L).
  2. Visited = removed. When we queue a word, remove it from the set. A word is queued once, at its shortest distance.

The solution in Java: BFS

import java.util.*;

public class Main {
    static 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 ArrayDeque<>();
        queue.add(beginWord);
        words.remove(beginWord);
        int steps = 1;
        while (!queue.isEmpty()) {
            for (int k = queue.size(); k > 0; k--) {
                char[] w = queue.poll().toCharArray();
                for (int i = 0; i < w.length; i++) {
                    char old = w[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        w[i] = c;
                        String next = new String(w);
                        if (next.equals(endWord)) return steps + 1;
                        if (words.remove(next)) queue.add(next);
                    }
                    w[i] = old;
                }
            }
            steps++;
        }
        return 0;
    }
    public static void main(String[] args) {
        List<String> a = List.of("hot", "dot", "dog", "lot", "log", "cog");
        List<String> b = List.of("hot", "dot", "dog", "lot", "log");
        System.out.println(ladderLength("hit", "cog", a));
        System.out.println(ladderLength("hit", "cog", b));
        List<String> c = List.of("hot", "dot", "dog", "cog", "xyz");
        System.out.println(ladderLength("hit", "xyz", c));
        System.out.println(ladderLength("hot", "dot", List.of("dot")));
    }
}
5
0
0
2
  • 5 and 0: the LeetCode examples.
  • 0: xyz is in the list, but no word is one letter away from it (unreachable).
  • 2: a one-step ladder, hot → dot.

How it works, line by line:

  • queue.size() is read once per level, so the inner loop processes exactly one level; steps counts the words in the ladder up to that level.
  • words.remove(next) returns true only if next was an unseen dictionary word, so it checks and marks visited in one call.
  • w[i] = old puts the letter back before trying the next position.

On the 125 words that timed out, and on all 4,096 four-letter words over a..h:

4 words, 2 ms
4096 words: 5 words in the ladder, 21 ms

(Times vary from run to run and machine to machine.)

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

// Word Ladder (LeetCode 127): BFS level by level; neighbours = change each letter a..z, checked in a hash set.
int ladderLength(string beginWord, string endWord, vector<string> wordList) {
    unordered_set<string> words(wordList.begin(), wordList.end());
    if (!words.count(endWord)) return 0;
    queue<string> q;
    q.push(beginWord);
    words.erase(beginWord);
    int steps = 1;
    while (!q.empty()) {
        for (int k = q.size(); k > 0; k--) {
            string w = q.front(); q.pop();
            for (size_t i = 0; i < w.size(); i++) {
                char old = w[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    w[i] = c;
                    if (w == endWord) return steps + 1;
                    if (words.erase(w)) q.push(w);
                }
                w[i] = old;
            }
        }
        steps++;
    }
    return 0;
}

int main() {
    vector<string> a = {"hot", "dot", "dog", "lot", "log", "cog"};
    vector<string> b = {"hot", "dot", "dog", "lot", "log"};
    cout << ladderLength("hit", "cog", a) << "\n";
    cout << ladderLength("hit", "cog", b) << "\n";
    cout << ladderLength("hit", "xyz", {"hot", "dot", "dog", "cog", "xyz"}) << "\n";
    cout << ladderLength("hot", "dot", {"dot"}) << "\n";
}
5
0
0
2

The same solution in Python

from collections import deque
from string import ascii_lowercase

# Word Ladder (LeetCode 127): BFS level by level; neighbours = change each letter a..z, checked in a set.
def ladder_length(begin_word, end_word, word_list):
    words = set(word_list)
    if end_word not in words:
        return 0
    queue = deque([begin_word])
    words.discard(begin_word)
    steps = 1
    while queue:
        for _ in range(len(queue)):
            w = queue.popleft()
            for i in range(len(w)):
                for c in ascii_lowercase:
                    nxt = w[:i] + c + w[i + 1:]
                    if nxt == end_word:
                        return steps + 1
                    if nxt in words:
                        words.remove(nxt)
                        queue.append(nxt)
        steps += 1
    return 0

print(ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]))
print(ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log"]))
print(ladder_length("hit", "xyz", ["hot", "dot", "dog", "cog", "xyz"]))
print(ladder_length("hot", "dot", ["dot"]))
5
0
0
2

Faster still: bidirectional BFS

Search from both ends and always grow the smaller frontier; stop when a new word is already in the other frontier. If each word has b neighbours and the ladder is d steps, one BFS touches about b^d words; two half searches touch about 2 · b^(d/2).

import java.util.*;

public class Main {
    // Bidirectional BFS: grow the smaller frontier; stop when it touches the other one.
    static 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)), back = new HashSet<>(List.of(endWord));
        words.remove(beginWord);
        words.remove(endWord);
        int steps = 1;
        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 s : front) {
                char[] w = s.toCharArray();
                for (int i = 0; i < w.length; i++) {
                    char old = w[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        w[i] = c;
                        String cand = new String(w);
                        if (back.contains(cand)) return steps + 1;
                        if (words.remove(cand)) next.add(cand);
                    }
                    w[i] = old;
                }
            }
            front = next;
            steps++;
        }
        return 0;
    }
    public static void main(String[] args) {
        System.out.println(ladderLength("hit", "cog", List.of("hot", "dot", "dog", "lot", "log", "cog")));
        System.out.println(ladderLength("hit", "cog", List.of("hot", "dot", "dog", "lot", "log")));
        System.out.println(ladderLength("hot", "dot", List.of("dot")));
    }
}
5
0
2

Three real bugs

Bug 1: not checking that endWord is in the list

Delete if (!words.contains(endWord)) return 0; and run the two examples:

5
5

Example 2 should be 0. The line if (next.equals(endWord)) return steps + 1; stepped onto cog, a word that isn't allowed.

Bug 2: never crossing words off

Check words.contains(next) instead of words.remove(next) (and never remove beginWord), with an end word that can't be reached:

                        if (next.equals(endWord) && words.contains(next)) return steps + 1;
                        if (words.contains(next)) queue.add(next);

On hit → xyz with [hot, dot, dog, cog, xyz]: Time Limit Exceeded in the compiler. hot → dot → hot → dot …: the queue grows every level and never empties. Given 44 seconds, Java fails with:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at Main.ladderLength(Main.java:16)
    at Main.main(Main.java:29)

Bug 3: counting moves instead of words

return steps; instead of return steps + 1;:

4
0

hit → hot → dot → dog → cog is 4 moves but 5 words; LeetCode asks for words.

Complexity

N = number of words, L = word length.

Approach Time Space 125 words 4,096 words
DFS over every path exponential O(N) path + recursion Time Limit Exceeded Time Limit Exceeded
BFS, compare every pair for neighbours O(N² · L) O(N · L) fast ~3.4 crore letter checks
BFS, change each letter + HashSet O(N · L · 26 · L) O(N · L) 2 ms 21 ms
Bidirectional BFS same worst case, far fewer words in practice O(N · L)

Why 26 · L · L: each visited word makes 26 · L candidates, and building and hashing each candidate string costs O(L).

Common mistakes

Mistake What you see (real) Why Fix
DFS for "fewest steps" Time Limit Exceeded tries every path BFS, level by level
endWord not checked 5 instead of 0 stepped on a word not in the list return 0 if it's missing
No visited marking TLE / OutOfMemoryError words queued again and again words.remove(next) when queueing
return steps 4 instead of 5 counted moves, not words return steps + 1
Marking visited when polled correct but slow the same word queued many times in one level mark when queued
Comparing with every word slow on 5,000 words O(N² · L) change each letter a..z
Forgetting w[i] = old wrong neighbours two letters changed restore the letter

Mini project: print the ladder itself

Keep a parent map (who discovered each word) and walk it back from endWord.

import java.util.*;

public class Main {
    // Mini project: BFS that remembers who discovered each word, then prints the ladder.
    static List<String> ladder(String begin, String end, List<String> list) {
        Set<String> words = new HashSet<>(list);
        Map<String, String> parent = new HashMap<>();
        Queue<String> q = new ArrayDeque<>(List.of(begin));
        words.remove(begin);
        while (!q.isEmpty()) {
            String cur = q.poll();
            if (cur.equals(end)) {
                LinkedList<String> path = new LinkedList<>();
                for (String s = end; s != null; s = parent.get(s)) path.addFirst(s);
                return path;
            }
            char[] w = cur.toCharArray();
            for (int i = 0; i < w.length; i++) {
                char old = w[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    w[i] = c;
                    String next = new String(w);
                    if (words.remove(next)) { parent.put(next, cur); q.add(next); }
                }
                w[i] = old;
            }
        }
        return List.of();
    }
    public static void main(String[] args) {
        List<String> dict = List.of("cord", "card", "ward", "warm", "word", "worm", "corm", "wold");
        System.out.println(ladder("cold", "warm", dict));
        System.out.println(ladder("hit", "cog", List.of("hot", "dot", "dog", "lot", "log", "cog")));
    }
}
[cold, wold, word, ward, warm]
[hit, hot, dot, dog, cog]

(With this dictionary BFS finds cold → wold → word → ward → warm first; Lewis Carroll's cold → cord → card → ward → warm is another 5-word ladder. BFS returns a shortest ladder; which one depends on the order letters are tried.)

Practice

1. Open the Lock (LeetCode 752). A lock has 4 wheels 0-9; each move turns one wheel one notch up or down (9 wraps to 0). Starting at "0000", avoid every deadends code; return the fewest moves to reach target, or -1.

Solution

The same implicit-graph BFS: each code has 8 neighbours (4 wheels × up/down).

import java.util.*;

public class Main {
    // Open the Lock (LeetCode 752): BFS over 4-digit codes; 8 neighbours each; deadends are pre-visited.
    static int openLock(String[] deadends, String target) {
        Set<String> seen = new HashSet<>(Arrays.asList(deadends));
        if (seen.contains("0000")) return -1;
        Queue<String> q = new ArrayDeque<>(List.of("0000"));
        seen.add("0000");
        for (int moves = 0; !q.isEmpty(); moves++)
            for (int k = q.size(); k > 0; k--) {
                String cur = q.poll();
                if (cur.equals(target)) return moves;
                char[] w = cur.toCharArray();
                for (int i = 0; i < 4; i++) {
                    char old = w[i];
                    for (int d : new int[]{1, 9}) {
                        w[i] = (char) ('0' + (old - '0' + d) % 10);
                        String next = new String(w);
                        if (seen.add(next)) q.add(next);
                    }
                    w[i] = old;
                }
            }
        return -1;
    }
    public static void main(String[] args) {
        System.out.println(openLock(new String[]{"0201", "0101", "0102", "1212", "2002"}, "0202"));
        System.out.println(openLock(new String[]{"8888"}, "0009"));
        System.out.println(openLock(new String[]{"8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"}, "8888"));
    }
}
6
1
-1

2. Minimum Genetic Mutation (LeetCode 433). Genes are 8-letter strings over A C G T; one mutation changes one letter and must land in bank. Return the fewest mutations from start to end, or -1.

Solution

Word ladder with a 4-letter alphabet, counting moves instead of words.

from collections import deque

# Minimum Genetic Mutation (LeetCode 433): BFS; alphabet ACGT; counts mutations (moves).
def min_mutation(start, end, bank):
    bank = set(bank)
    if end not in bank:
        return -1
    q, moves = deque([start]), 0
    bank.discard(start)
    while q:
        for _ in range(len(q)):
            g = q.popleft()
            if g == end:
                return moves
            for i in range(len(g)):
                for c in "ACGT":
                    nxt = g[:i] + c + g[i + 1:]
                    if nxt in bank:
                        bank.remove(nxt)
                        q.append(nxt)
        moves += 1
    return -1

print(min_mutation("AACCGGTT", "AACCGGTA", ["AACCGGTA"]))
print(min_mutation("AACCGGTT", "AAACGGTA", ["AACCGGTA", "AACCGCTA", "AAACGGTA"]))
print(min_mutation("AAAAACCC", "AACCCCCC", ["AAAACCCC", "AAACCCCC", "AACCCCCC"]))
1
2
3

3. Word Ladder II (LeetCode 126). Print all shortest ladders. Hint: run BFS level by level, and for each word record every parent from the previous level (remove words from the set only after the whole level is done); then DFS backwards from endWord over the parent lists.

4. Return the ladder length in C++ with bidirectional BFS. Hint: use two unordered_set<string>s and swap them when the front one is bigger, exactly like the Java version above.

Quick quiz

beginWord = "cat", endWord = "dog", wordList = [cot, cog, dot, dog]. What does ladderLength return? A) 4 B) 3 C) 5 D) 0

Answer

A) 4. cat → cot → cog → dog (or cat → cot → dot → dog). A 3-word ladder would need a word one letter from both cat and dog; there is none.

Interview questions

  1. Why BFS and not DFS? All edges cost one step, and BFS reaches every node first along a shortest path; DFS finds a path and must explore everything to be sure it's shortest.
  2. What is an implicit graph? One whose edges are generated from a rule on demand, instead of being stored.
  3. How do you find a word's neighbours quickly? Change each position to a..z and look it up in a hash set: 26 · L lookups instead of comparing with all N words.
  4. Why mark visited when queueing, not when polling? Otherwise the same word can be queued many times by different words of the same level.
  5. What does bidirectional BFS save? About b^d work becomes about 2 · b^(d/2), because two searches of half depth meet in the middle.
  6. Complexity? O(N · L² · 26) time and O(N · L) space.
  7. Would Dijkstra work? Yes, but with equal weights it does the same thing as BFS, only slower (log factor for the heap).

Glossary

Term Meaning
Word ladder / transformation sequence Words from begin to end, one letter changed per step
Node, edge A thing; a link between two things
Unweighted graph Every edge costs the same
Implicit graph Neighbours generated by a rule when needed
DFS Go deep down one path, then backtrack
Backtracking Undo the last choice to try another
BFS Explore by distance: 1 step, 2 steps, … with a queue
Level All nodes at the same distance from the start
Queue First in, first out (ArrayDeque)
HashSet Set with O(1) average add / contains / remove
Visited Already queued; never queued again
Bidirectional BFS BFS from both ends, meeting in the middle
Frontier The nodes of the current BFS level

Summary

  • Words are nodes; one letter apart is an edge. The graph is implicit: we make neighbours on demand.
  • DFS over every path is correct but exponential: Time Limit Exceeded on 125 words.
  • Fewest steps with equal edges means BFS: the first time it reaches endWord is the answer (count words: steps + 1).
  • Neighbours: change each letter a..z and check a HashSet; remove = visited.
  • Watch for: endWord not in the list, never marking visited, and counting moves instead of words.
  • Next episode: strongly connected components and bridges (hard): one-way streets, and the roads a city can't afford to lose.