Introduction

A five-letter word chain is a shortest-path problem in disguise. Each word is a node, two words are connected if they differ by exactly one letter, and breadth-first search is the natural algorithm because it finds the shortest path in an unweighted graph.

Model the Puzzle as a Graph

Suppose you want to transform one five-letter word into another by changing one letter at a time, always staying inside a valid dictionary. For example:

• start word: stone
• end word: money
• valid intermediate words must also be real five-letter words

That is a graph problem:

• each word is a vertex
• an edge exists when two words differ by one character
• the desired chain is the shortest path from start to target

Because every edge has equal cost, BFS is the correct shortest-path algorithm.

A Direct BFS Solution

A straightforward implementation generates neighbors by trying all one-letter substitutions and checking whether the result is in the dictionary set.

1from collections import deque
2import string
3
4
5def neighbors(word, word_set):
6    for i in range(len(word)):
7        for ch in string.ascii_lowercase:
8            if ch == word[i]:
9                continue
10            candidate = word[:i] + ch + word[i + 1:]
11            if candidate in word_set:
12                yield candidate
13
14
15def shortest_chain(start, target, words):
16    word_set = set(words)
17    if target not in word_set:
18        return None
19
20    queue = deque([start])
21    parent = {start: None}
22
23    while queue:
24        word = queue.popleft()
25        if word == target:
26            break
27
28        for nxt in neighbors(word, word_set):
29            if nxt not in parent:
30                parent[nxt] = word
31                queue.append(nxt)
32
33    if target not in parent:
34        return None
35
36    path = []
37    current = target
38    while current is not None:
39        path.append(current)
40        current = parent[current]
41
42    return list(reversed(path))
43
44
45dictionary = {"stone", "shone", "phone", "phony", "money"}
46print(shortest_chain("stone", "money", dictionary))

This works because BFS explores all words at distance 1, then all words at distance 2, and so on. The first time it reaches the target, the discovered chain is shortest.

Why BFS Is the Right Choice

Depth-first search can find a chain, but it does not guarantee the shortest one. BFS does, as long as every step counts equally.

That makes BFS ideal for word-ladder or word-chain puzzles because each letter change is just one move. You are not optimizing weighted cost or probability. You are minimizing the number of transformations.

Reconstructing the Path

The parent dictionary is the key to turning BFS from a yes-or-no reachability test into an actual chain generator. Every time BFS discovers a new word, it records which previous word led to it.

Once the target is found, walking backward through parent reconstructs the path. Without that record, BFS could still tell you the distance, but not the actual transformation chain.

Performance Considerations

The naive neighbor generator is often fine for small puzzles, but large dictionaries can make it expensive because each visited word tries many candidate mutations.

A common optimization is to precompute wildcard buckets. For example, stone contributes patterns such as:

• '_tone'
• 's_one'
• 'st_ne'
• 'sto_e'
• 'ston_'

Words that share a wildcard pattern differ by one letter at one position, so those buckets make neighbor lookup much faster.

That optimization is not required to understand BFS, but it matters if the dictionary is large.

Common Pitfalls

Using depth-first search when the real requirement is the shortest chain can produce correct-looking but unnecessarily long paths.

Forgetting to mark visited words allows the search to revisit the same nodes and can create massive slowdowns or loops.

Not storing parent pointers means you can discover the target but still fail to reconstruct the chain itself.

Allowing words of mixed length breaks the graph model because the one-letter-change rule assumes a consistent word size.

Treating the dictionary as a list instead of a set makes membership checks much slower than they need to be.

Summary

• A five-letter word chain is naturally modeled as an unweighted graph.
• BFS is the right algorithm because it finds the shortest path.
• Use a queue for traversal and a parent map to reconstruct the chain.
• Store the dictionary in a set for fast membership checks.
• Precomputed wildcard buckets can speed up neighbor lookup on large word lists.