← MakeMyTrip questions

Transform string using intermediate string array

Filed under MakeMyTrip

Free read 3 of 3

Treat 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

  1. Treat words as nodes and edges exist if words differ by one character.

Solution

O(M^2 * N) time, O(M * N) space

Python
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.