Word Ladder Length
Given beginWord, endWord, and a word list, return the length of the shortest transformation sequence from begin to end changing one letter at a time, each intermediate in the word list. Return 0 if impossible.
Answers use simple, clear English.
Quick interview answer
BFS where each word is a node and edges connect Hamming-distance-1 words. Use a set for O(1) membership; optionally generate neighbors by trying 26 letters per position. Bidirectional BFS optimizes further.
Detailed answer
BFS where each word is a node and edges connect Hamming-distance-1 words. Use a set for O(1) membership; optionally generate neighbors by trying 26 letters per position. Bidirectional BFS optimizes further. DFS is wrong for shortest path in unweighted graphs.
Full explanation
DFS is wrong for shortest path in unweighted graphs.
Real example & use case
Password-migration helper estimating minimum edits between policy-compliant dictionary words.
Pros & cons
Pros: BFS guarantees shortest. Cons: neighbor generation can be hot — pattern dictionaries help.
Code example
from collections import deque
def ladder_length(begin: str, end: str, word_list: list[str]) -> int:
words = set(word_list)
if end not in words:
return 0
q = deque([(begin, 1)])
seen = {begin}
while q:
word, dist = q.popleft()
if word == end:
return dist
for i in range(len(word)):
for ch in 'abcdefghijklmnopqrstuvwxyz':
nxt = word[:i] + ch + word[i + 1:]
if nxt in words and nxt not in seen:
seen.add(nxt)
q.append((nxt, dist + 1))
return 0Practice code · python (view only · no execution)
from collections import deque
def ladder_length(begin: str, end: str, word_list: list[str]) -> int:
words = set(word_list)
if end not in words:
return 0
q = deque([(begin, 1)])
seen = {begin}
while q:
word, dist = q.popleft()
if word == end:
return dist
for i in range(len(word)):
for ch in 'abcdefghijklmnopqrstuvwxyz':
nxt = word[:i] + ch + word[i + 1:]
if nxt in words and nxt not in seen:
seen.add(nxt)
q.append((nxt, dist + 1))
return 0