TL;DR
Model words as nodes with one-edit edges; BFS for the shortest chain, optionally sped up with wildcard buckets or bidirectional search — O(N · L²) time, O(N · L²) space (N words, L word length).
Approach 1 — BFS generating neighbors on the fly
Adjacent words differ by exactly one letter and every edge costs one step, so this is an unweighted shortest-path problem: run BFS from beginWord, expanding level by level. To find a word’s neighbors, replace each of its L positions with each of the 26 letters and keep the candidates that are in the word set. The first time BFS reaches endWord, the level count is the shortest sequence length. DFS does not work here: it can reach endWord down a long chain that is not the shortest one.
from collections import deque
def ladderLength(beginWord: str, endWord: str, wordList: list[str]) -> int:
words = set(wordList)
if endWord not in words:
return 0
alphabet = "abcdefghijklmnopqrstuvwxyz"
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
if word == endWord:
return steps
for i in range(len(word)):
for ch in alphabet:
cand = word[:i] + ch + word[i + 1:]
if cand in words and cand not in visited:
visited.add(cand)
queue.append((cand, steps + 1))
return 0
Walkthrough ("hit" → "cog", list ["hot","dot","dog","lot","log","cog"]): level 1 is hit. Its one valid neighbor is hot → level 2. From hot, neighbors dot and lot → level 3. From those, dog and log → level 4. From dog/log, cog appears → dequeued at level 5. Answer 5.
The example forms this graph; BFS levels are the distance from hit:
graph LR
hit --- hot
hot --- dot
hot --- lot
dot --- dog
lot --- log
dog --- cog
log --- cog
Complexity: each of N words spawns L × 26 candidate strings, and building/hashing each costs O(L) → O(N · L² · 26) = O(N · L²) time, O(N · L) space for the queue and visited set. Simple and fast enough for typical inputs.
Approach 2 — Wildcard (pattern) adjacency
Instead of generating 26 candidates per position, precompute an adjacency index. For every word, generate L wildcard patterns by masking one position (hot → *ot, h*t, ho*). Two words are one edit apart iff they share a pattern, so each pattern bucket is a group of mutual neighbors. BFS then looks up neighbors directly by pattern.
from collections import deque, defaultdict
def ladderLength(beginWord: str, endWord: str, wordList: list[str]) -> int:
words = set(wordList)
if endWord not in words:
return 0
L = len(beginWord)
buckets = defaultdict(list)
for word in words | {beginWord}:
for i in range(L):
buckets[word[:i] + "*" + word[i + 1:]].append(word)
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
if word == endWord:
return steps
for i in range(L):
key = word[:i] + "*" + word[i + 1:]
for nxt in buckets[key]:
if nxt not in visited:
visited.add(nxt)
queue.append((nxt, steps + 1))
return 0
Walkthrough (same input): hot, dot, lot all land in bucket *ot; dot/dog share do*; dog/log/cog share *og. BFS from hit (patterns *it, h*t, hi*) reaches hot via h*t, then hops through the shared buckets, arriving at cog at level 5.
Complexity: building the index is O(N · L²) (each of N words makes L patterns of length L). BFS visits each word once and each pattern bucket once → O(N · L²) time and space overall. Same big-O as Approach 1 but avoids the ×26 constant and repeated membership probing.
Approach 3 — Bidirectional BFS
A BFS frontier grows exponentially with depth, so searching d levels from one side explores far more nodes than searching d/2 from each side. Bidirectional BFS grows two frontiers, one from beginWord and one from endWord, and stops as soon as they meet. Always expanding the smaller frontier keeps the work minimal.
def ladderLength(beginWord: str, endWord: str, wordList: list[str]) -> int:
words = set(wordList)
if endWord not in words:
return 0
alphabet = "abcdefghijklmnopqrstuvwxyz"
front, back = {beginWord}, {endWord}
words.discard(beginWord)
steps = 1
while front and back:
if len(front) > len(back):
front, back = back, front
nxt = set()
for word in front:
for i in range(len(word)):
for ch in alphabet:
cand = word[:i] + ch + word[i + 1:]
if cand in back:
return steps + 1
if cand in words:
words.discard(cand)
nxt.add(cand)
front = nxt
steps += 1
return 0
Walkthrough (same input): front = {hit}, back = {cog}. Expanding hit gives {hot} (steps→2). back = {cog} is now the smaller/equal set — expand it to {dog, log} (steps→3). Expand {hot}’s side to {dot, lot}; generating from these produces dog, which is in back → return steps + 1. The two waves meet in the middle at total length 5.
Complexity: same worst-case O(N · L²), but in practice it touches roughly the square root of the nodes a one-directional BFS would, a large constant-factor win on big lists.
Common pitfalls
endWord not in wordList. Check up front and return 0 — otherwise BFS wanders the whole graph and still fails.- Counting edges instead of words. The answer includes both endpoints, so a direct one-edit hop returns
2, not 1. Start the counter at 1.
- Marking visited on dequeue. In BFS, add a word to
visited when you enqueue it; deferring to dequeue lets the same word enter the queue multiple times at the same level and can inflate work or double-count.
beginWord in the set. It need not be in wordList; don’t require it, and don’t let it be re-added mid-search.- Bidirectional swap. Forgetting to always expand the smaller frontier, or checking membership against the wrong side, breaks the meet-in-the-middle guarantee.
Pattern takeaway
“Fewest single-letter/single-move transformations” is shortest path on an unweighted graph: use BFS, not DFS, since only BFS’s level-order expansion guarantees the minimum. When neighbor generation dominates, precompute an adjacency index (wildcard buckets); when the graph is large and both endpoints are known, bidirectional BFS reduces the search depth and the number of nodes explored.