Difficulty: Hard | Asked at: Google, Amazon, LinkedIn
Given
beginWord, endWord, and a word list, find the length of the shortest transformation sequence, changing one letter at a time, where each intermediate word must exist in the word list.
Input: beginWord = "hit", endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5 ("hit" -> "hot" -> "dot" -> "dog" -> "cog")
💡 Hint: "Shortest transformation" is your biggest clue - this is shortest path in an unweighted graph, which means BFS, not DFS.
Solution:
python
from collections import deque
def ladder_length(begin_word, end_word, word_list):
word_set = set(word_list)
if end_word not in word_set:
return 0
queue = deque([(begin_word, 1)])
visited = {begin_word}
while queue:
word, steps = queue.popleft()
if word == end_word:
return steps
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = word[:i] + c + word[i+1:]
if next_word in word_set and next_word not in visited:
visited.add(next_word)
queue.append((next_word, steps + 1))
return 0
Complexity: O(M² × N) time, where M is word length and N is the word list size - for each word, we try M positions × 26 letters, each generating an M-length string.
Common mistake: Reaching for DFS because it "feels" more natural for pathfinding - DFS can find A path, but has no guarantee it finds the SHORTEST one without exploring everything. The moment you see "shortest" or "minimum steps" in unweighted graph problems, that's your signal: BFS.
This is one of those problems where recognizing the underlying pattern (shortest path = BFS) matters far more than clever tricks - the "graph" here isn't even given to you explicitly, you have to realize that words are nodes and one-letter-difference is an edge.
Did you recognize this as a graph problem right away, or did it take a second to see it? 👇