Description
Transform beginWord into endWord by changing exactly one lowercase letter per step. Every resulting word must be in wordList. Return the number of words in the shortest transformation, or zero if none exists. Words have equal length and beginWord differs from endWord.
Solution
from collections import deque
def ladder_length(begin_word, end_word, word_list):
remaining = set(word_list)
if end_word not in remaining:
return 0
remaining.discard(begin_word)
queue = deque([(begin_word, 1)])
while queue:
word, distance = queue.popleft()
if word == end_word:
return distance
for i in range(len(word)):
for ch in "abcdefghijklmnopqrstuvwxyz":
candidate = word[:i] + ch + word[i + 1:]
if candidate in remaining:
remaining.remove(candidate)
queue.append((candidate, distance + 1))
return 0Examples
Example 1
- Input
["hit","cog",["hot","dot","dog","lot","log","cog"]]- Output
5
hit-hot-dot-dog-cog uses five words.
Example 2
- Input
["hit","cog",["hot","dot","dog","lot","log"]]- Output
0
endWord is not in the dictionary.
Example 3
- Input
["a","c",["a","b","c"]]- Output
2
Changing a directly to c takes one step and two words.
Approach
Run BFS from beginWord. Generate neighbors by trying each alphabet letter at each position, retaining only dictionary words. Remove a word from the unvisited set when enqueued so its first visit is shortest.
Time & space
O(N L^2 A) time and O(N L) auxiliary space, where N is word count, L is word length, and A = 26; constructing and hashing a neighbor costs O(L).