The Chain Transform

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L5
Asked in
Citadel

Problem

Given a start word, an end word, and a dictionary of words, compute the length of the shortest transformation sequence that changes the start word into the end word, where each step changes exactly one letter and every intermediate word must appear in the dictionary. Return the number of words in that shortest sequence, counting BOTH the start and end words (for example, hit -> hot -> dot -> dog -> cog has length 5). Return 0 if no such transformation exists.

One small step at a time can cover a great distance.

Example 1

Input:

begin_word = "hit", end_word = "cog", word_list = ["hot","dot","dog","lot","log","cog"]

Output:

5

Example 2

Input:

begin_word = "hit", end_word = "cog", word_list = ["hot","dot","dog","lot","log"]

Output:

0

Worked solution and explanation

Why this problem exists in real interviews

Word ladder (minimum transformations) tests BFS on an implicit graph where nodes are words and edges connect words differing by one letter. It is a classic graph search problem that checks BFS implementation skills.

Break down the requirements

Step 1: Treat each valid word as a graph node

Two words are connected if they differ by exactly one character.

Step 2: BFS from start to end

BFS guarantees the shortest path in an unweighted graph. Carry a count of how many words are in the path so far; the start word counts as 1.

Step 3: Count nodes, and return 0 if no path exists

Return the number of WORDS in the shortest sequence, including the start and end words (nodes), not the number of one-letter changes (edges). If BFS exhausts all reachable words without finding the end, return 0.

The solution

BFS word ladder counting words (nodes) in the shortest sequence
from collections import deque

def word_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, length = queue.popleft()
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + c + word[i+1:]
                if next_word == end_word:
                    return length + 1
                if next_word in word_set and next_word not in visited:
                    visited.add(next_word)
                    queue.append((next_word, length + 1))
    return 0

Common follow-up questions