Word Ladder (LeetCode 127) is the canonical example of BFS on an implicit graph — the nodes are words, the edges are single-letter transformations. It appears frequently at Google, Facebook, and Microsoft because it tests your ability to model abstract problems as graphs.
Problem
Given a beginWord, an endWord, and a wordList, find the length of the shortest transformation sequence from beginWord to endWord. Each step can change exactly one letter, and each intermediate word must be in wordList.
beginWord = "hit", endWord = "cog" wordList = ["hot","dot","dog","lot","log","cog"] hit → hot → dot → dog → cog (5 words, length = 5)
Why BFS, Not DFS
DFS would find A path, but not necessarily the shortest. BFS explores all paths of length k before exploring paths of length k+1, so the first time it reaches the endWord is via the shortest path.
Solution: BFS with Wildcard Neighbors
from collections import defaultdict, deque
def ladder_length(begin_word: str, end_word: str, word_list: list[str]) -> int:
"""
BFS on implicit graph: nodes = words, edges = single letter differences.
Key optimization: pre-build adjacency using wildcard patterns.
e.g., "hot" → "*ot", "h*t", "ho*" — group words by their patterns.
Time: O(M^2 * N) where M = word length, N = wordList size
"""
word_set = set(word_list)
if end_word not in word_set:
return 0
# Build wildcard pattern groups: "*ot" → ["hot", "dot", "lot"]
pattern_map = defaultdict(list)
for word in word_list:
for i in range(len(word)):
pattern = word[:i] + '*' + word[i+1:]
pattern_map[pattern].append(word)
queue = deque([(begin_word, 1)]) # (word, steps)
visited = {begin_word}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
pattern = word[:i] + '*' + word[i+1:]
for neighbor in pattern_map[pattern]:
if neighbor == end_word:
return steps + 1
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, steps + 1))
return 0 # No path foundBidirectional BFS (Optimization)
Instead of searching from start only, expand from both start and end simultaneously. When the frontiers meet, we have the shortest path. This reduces time complexity from O(b^d) to O(b^(d/2)) where b is branching factor and d is distance.
def ladder_length_bidirectional(begin_word: str, end_word: str, word_list: list[str]) -> int:
"""
Bidirectional BFS: expand from both begin and end simultaneously.
Meet in the middle for O(b^(d/2)) vs O(b^d) complexity.
"""
word_set = set(word_list)
if end_word not in word_set:
return 0
def get_neighbors(word):
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word != word and new_word in word_set:
yield new_word
# Two frontiers
front = {begin_word: 1} # word -> distance from begin
back = {end_word: 1} # word -> distance from end
visited = {begin_word, end_word}
while front and back:
# Always expand the smaller frontier
if len(front) > len(back):
front, back = back, front
next_front = {}
for word, dist in front.items():
for neighbor in get_neighbors(word):
if neighbor in back:
return dist + back[neighbor] # Frontiers met!
if neighbor not in visited:
visited.add(neighbor)
next_front[neighbor] = dist + 1
front = next_front
return 0
print(ladder_length("hit", "cog", ["hot","dot","dog","lot","log","cog"])) # 5Word Ladder II — All Shortest Paths (LeetCode 126)
from collections import defaultdict, deque
def find_ladders(begin_word: str, end_word: str, word_list: list[str]) -> list[list[str]]:
"""
Return ALL shortest transformation sequences.
Strategy: BFS to find shortest distance, then DFS to collect all paths.
"""
word_set = set(word_list)
if end_word not in word_set:
return []
# BFS to build layer graph
layer = {begin_word}
parents = defaultdict(set) # child -> set of parents (who led here)
found = False
while layer and not found:
word_set -= layer # Remove current layer to prevent backward traversal
next_layer = set()
for word in layer:
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word in word_set:
next_layer.add(new_word)
parents[new_word].add(word)
if new_word == end_word:
found = True
layer = next_layer
if not found:
return []
# DFS to collect all paths
result = []
def dfs(word, path):
if word == begin_word:
result.append(list(reversed(path)))
return
for parent in parents[word]:
path.append(parent)
dfs(parent, path)
path.pop()
dfs(end_word, [end_word])
return resultThe Implicit Graph Pattern
Word Ladder is the template for problems where the graph is too large to store explicitly — you generate neighbors on the fly:
- Word transformation graphs
- Sliding puzzle (8-puzzle, 15-puzzle): each board state is a node
- Chemical reaction chains
- Knight moves on a chessboard (BFS to find minimum moves)
Related Graph Topics
- BFS vs DFS — Word Ladder requires BFS for shortest path; DFS would find a path but not necessarily the shortest transformation sequence
- Number of Islands — both are BFS/DFS on graphs; islands uses an explicit grid, word ladder uses an implicit graph generated by single-letter transformations