Transform string using intermediate string array
Filed under MakeMyTrip
Free read 3 of 3Treat words as nodes and edges exist if words differ by one character.
The question
Given a start string, an end string, and a dictionary of words, find the shortest transformation sequence from start to end, changing one character at a time, where each intermediate word exists in the dictionary.
Constraints
- All words are of the same length.
- Return the length of the shortest sequence or 0 if none exists.
- The dictionary is provided as a list.
Examples
- Input
- begin='hit', end='cog', dict=['hot','dot','dog','lot','log','cog']
- Output
- 5
- Why
- hit -> hot -> dot -> dog -> cog is length 5.
Approach
Treat words as nodes and edges exist if words differ by one character.
Use BFS to find the shortest path in an unweighted graph.
Pre-process dictionary into a set for O(1) lookups and generate neighbors by changing each character.
Solution
O(M^2 * N) time, O(M * N) space
from collections import deque
def ladderLength(begin, end, wordList):
wordSet = set(wordList)
queue = deque([(begin, 1)])
while queue:
word, dist = queue.popleft()
if word == end: return dist
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_w = word[:i] + c + word[i+1:]
if next_w in wordSet:
wordSet.remove(next_w)
queue.append((next_w, dist + 1))
return 0
Tips
- What they are testing: Test with no possible path and a direct transformation.
- Common mistake: Using DFS instead of BFS, which does not guarantee the shortest path.
Related MakeMyTrip questions
Collected from public candidate posts and coding forums. Updated Nov 2026.