Word Ladder Steps
Problem
Given a starting word, a target word, and a dictionary of allowed words, transform the start into the target by changing one letter at a time. Every intermediate word, and the target itself, must appear in the dictionary, and all words share the same length. Return the number of words in the shortest chain including both ends, or 0 when no chain exists.
Examples
Input: start = hit, target = cog, words = [hot, dot, dog, lot, log, cog]
Output: 5
Why: hit, hot, dot, dog, cog is five words longInput: start = hit, target = cog, words = [hot, dot, dog]
Output: 0
Why: the target is missing from the dictionary, so nothing can reach itInput: start = a, target = c, words = [a, b, c]
Output: 2
Why: edge case, single letters let the start reach the target directlyHints
0 / 3
Think of each allowed word as a place and each single-letter change as a road between two places. The question is then about distance, not about words.
All roads cost the same, so exploring outward in rings from the start reaches every word by the fewest changes possible. Depth-first wandering would not.
Explore in rings from the starting word, generating neighbours by replacing each position with every letter of the alphabet and keeping only those in the dictionary. Remove a word from the dictionary the first time it is reached, since a later arrival can never be shorter, and stop as soon as the target comes up.
Solution
Words are nodes and single-letter edits are unweighted edges, so a breadth-first exploration finds the shortest chain. Neighbours are generated by substituting every letter at every position and keeping the results that exist in the dictionary, which is cheaper than comparing all pairs of words. Deleting a word on first arrival marks it visited and prevents the queue from revisiting it, since the first arrival is always the shortest. Time is O(N times L times 26) for N words of length L, and space is O(N times L).
from collections import deque
from string import ascii_lowercase
def ladder_length(start, target, words):
pool = set(words)
if target not in pool: return 0 # an unreachable target ends it early
q = deque([(start, 1)]) # word plus the chain length so far
while q:
word, steps = q.popleft()
if word == target: return steps
for i in range(len(word)):
for ch in ascii_lowercase: # try every single-letter edit
nxt = word[:i] + ch + word[i+1:]
if nxt in pool:
pool.remove(nxt) # first arrival is the shortest
q.append((nxt, steps + 1))
return 0
print(ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])) # -> 5
print(ladder_length("hit", "cog", ["hot", "dot", "dog"])) # -> 0
print(ladder_length("a", "c", ["a", "b", "c"])) # -> 2Stuck on the idea rather than the code? Shortest Path, Unweighted covers it.