Change one letter at a time to reach the end word. Treat words as a graph and search breadth first, so the first hit is the shortest.
▼The problem
LeetCode 127 (Hard). Given beginWord, endWord and a wordList, find the shortest transformation sequence from beginWord to endWord that changes one letter at a time, where every word after beginWord is in wordList. Return the number of words in it, or 0 if there is none.
Example: hit → cog with [hot, dot, dog, lot, log, cog] → 5 (hit → hot → dot → dog → cog).
The solution
def ladder_length(begin, end, word_list):
words = set(word_list)
if end not in words:
return 0
queue = deque([(begin, 1)])
seen = {begin}
while queue:
word, steps = queue.popleft()
if word == end:
return steps
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
nxt = word[:i] + c + word[i+1:]
if nxt in words and nxt not in seen:
seen.add(nxt)
queue.append((nxt, steps + 1))
return 0Transcript
Word Ladder. Change one word into another, one letter at a time, using only words from the list. Return the number of words in the shortest ladder, or zero if there's none.
Take hit to cog, with hot, dot, dog, lot, log and cog. Hit, hot, dot, dog, cog: five words. Without cog in the list: zero.
The naive way tries every sequence with depth-first search, and keeps the shortest. That's exponential.
The key idea: words are nodes, linked when they're one letter apart. The shortest ladder is a shortest path, so use breadth-first search, level by level. For neighbours, try all twenty-six letters at each position. A seen set stops repeats. The first time we reach the end word, that's the shortest ladder.
In code: a set of words, and zero if the end is missing. Queue the begin word at step one. Pop a word; if it's the end, return its steps. Otherwise, try each letter at each position, and queue unseen words with one more step.
Let's climb from hit, floor one. Change the middle letter: hot, floor two. Change the first: dot and lot, floor three. Then dog and log, floor four. From dog, d to c: cog, floor five. Log reaches cog too, but it's already seen. Cog is the end, so the answer is five.
Each of n words is visited once, trying twenty-six letters at each of L positions: n times L times twenty-six, or n times L squared with the string building. The queue and set hold n words: n times L space.
One rung per word, one letter per step, floor by floor. That's Word Ladder.