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
The insight: adjacent words differ by exactly one letter and every edge costs one step, so this is an unweighted shortest-path problem — 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 live in the word set. The first time BFS reaches endWord, the level count is the shortest sequence length. (DFS is unsuitable — it would wander down long chains without any guarantee of finding the shortest one.)
from collections import deque
class Solution:
def ladderLength(self, 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.
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. Correct and usually fast enough.
Approach 2 — Wildcard (pattern) adjacency
The insight: instead of manufacturing 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 clique of neighbors. BFS then looks up neighbors directly by pattern.
from collections import deque, defaultdict
class Solution:
def ladderLength(self, 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
The insight: a breadth-first frontier fans out 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, one from endWord — and stops the instant they touch. Always expanding the smaller frontier keeps the work minimal.
class Solution:
def ladderLength(self, 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 — reach for 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 halves the search depth and slashes the explored frontier.