The machine must find the shortest chain of words from beginWord to endWord where each step changes exactly one letter and every intermediate word is in the word list. The chain length counts the number of words, begin included, and 0 means no chain exists.
The key insight is to view this as an unweighted graph problem: words are nodes and edges connect words differing by one letter. Shortest path in an unweighted graph is BFS territory, which guarantees the first time the machine reaches endWord is via the shortest chain — no Dijkstra needed.
The approach has three steps. First, store the word list in a set so membership checks are O(1), and handle the trivial case where endWord is not in the set. Second, run BFS from beginWord, and for each word generate all one-letter mutations by replacing each position with all 26 letters; any mutation found in the set is a real neighbor. Third, track depth per word and return the depth when endWord is dequeued, or 0 if the queue empties first. With n words of length L, time is O(n × L × 26) and space is O(n).
The trickiest edge case is the target never appearing in the word list: the machine must return 0 immediately instead of running BFS forever. Self-mutations like 'hit' → 'hit' must not be re-enqueued — the visited set blocks them.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
words = set(wordList)
if endWord not in words:
return 0
q = deque([(beginWord, 1)])
while q:
word, depth = q.popleft()
if word == endWord:
return depth
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
nxt = word[:i] + c + word[i+1:]
if nxt in words:
words.remove(nxt)
q.append((nxt, depth + 1))
return 0