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 everysiis inwordList.beginWorddoes 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) averagecontains,addandremove(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
- Words are nodes; one letter apart is an edge. Example 1:
dot ── dog
/ | | \
hit ── hot | | cog
\ | | /
lot ── log
- 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 |
- Neighbours on demand. Comparing a word with all
Nwords costsO(N · L)per word,O(N² · L)in total. Instead, change each of theLletters to each ofa..z: only26 · Lcandidates (260 for a 10-letter word), each checked in aHashSetin O(L). - 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
5and0: the LeetCode examples.0:xyzis 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;stepscounts the words in the ladder up to that level.words.remove(next)returnstrueonly ifnextwas an unseen dictionary word, so it checks and marks visited in one call.w[i] = oldputs 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
- 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.
- What is an implicit graph? One whose edges are generated from a rule on demand, instead of being stored.
- How do you find a word's neighbours quickly? Change each position to
a..zand look it up in a hash set:26 · Llookups instead of comparing with allNwords. - Why mark visited when queueing, not when polling? Otherwise the same word can be queued many times by different words of the same level.
- What does bidirectional BFS save? About
b^dwork becomes about2 · b^(d/2), because two searches of half depth meet in the middle. - Complexity?
O(N · L² · 26)time andO(N · L)space. - Would Dijkstra work? Yes, but with equal weights it does the same thing as BFS, only slower (
logfactor 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
endWordis the answer (count words:steps + 1). - Neighbours: change each letter
a..zand check aHashSet;remove= visited. - Watch for:
endWordnot 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.