# The Chain Transform

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

Canonical URL: <https://datadriven.io/problems/the_chain_transform>

Domain: Python · Difficulty: medium · Seniority: L5

## Problem

Given a start word, an end word, and a dictionary of words, compute the minimum number of single-letter changes to transform start into end, where every intermediate word must also be in the dictionary. Return the number of words in the shortest transformation sequence (including start and end). Return 0 if no transformation exists.

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

> **Trick to Solving**
>
> Build a BFS from the start word. At each step, generate all possible one-letter transformations and check if they are in the dictionary. Use a visited set to avoid cycles. The first time you reach the end word, you have the shortest path.

---

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

#### Step 3: Return 0 if no path exists

If BFS exhausts all reachable words without finding the end, return 0.

---

### The solution

**BFS word ladder with character-by-character neighbor generation**

```python
from collections import deque
def word_ladder(start, end, word_list):
    word_set = set(word_list)
    if end not in word_set:
        return 0
    queue = deque([(start, 1)])
    visited = set()
    visited.add(start)
    while queue:
        word, steps = queue.popleft()
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + c + word[i+1:]
                if next_word == end:
                    return steps
                if next_word in word_set and next_word not in visited:
                    visited.add(next_word)
                    queue.append((next_word, steps + 1))
    return 0
```

> **Time and Space Complexity**
>
> **Time:** O(n * L * 26) where n is the dictionary size and L is the word length. For each word, we try 26 replacements at each of L positions.
> 
> **Space:** O(n) for the word set and visited set.

> **Interviewers Watch For**
>
> Using BFS (not DFS) since BFS finds the shortest path. Also, generating neighbors by trying all 26 characters at each position rather than comparing every pair of dictionary words (which would be O(n^2 * L)).

> **Common Pitfall**
>
> Using DFS, which finds a path but not necessarily the shortest one. BFS is required for minimum transformations.

---

## Common follow-up questions

- How would you return the actual transformation sequence? _(Tests tracking the path by storing parent pointers or the full path at each BFS node.)_
- What if you needed all shortest paths? _(Tests not pruning visited nodes until the current BFS level is complete.)_
- How would bidirectional BFS improve performance? _(Tests starting BFS from both ends and meeting in the middle, reducing the search space quadratically.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_chain_transform)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.