Fewest one-letter changes between two code words

Graphs Senior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
word = "cat"
allowed = {"cot", "cut", "bat", "dog"}
next_words = sorted(word[:i] + ch + word[i + 1:]
                    for i in range(len(word))
                    for ch in "abcdefghijklmnopqrstuvwxyz"
                    if word[:i] + ch + word[i + 1:] in allowed)
print(next_words)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A ['bat', 'cot', 'cut']

Right: each differs from 'cat' in exactly one letter.

Trying each position with each letter finds one-letter neighbours without comparing every pair of words.

Why not the others?
  • B ['bat', 'cot', 'cut', 'dog']. 'dog' differs in all three letters.
  • C ['cot', 'cut']. Changing the first letter gives 'bat', which is allowed.

30-second answer

Treat each word as a node and connect words that differ in one letter. BFS from the start gives the shortest chain. To find neighbours quickly, try every position and every letter: 26·L candidates per word of length L, each checked against a set. With N words that is O(N·26·L²) once string building is counted, and the set and queue take O(N·L) space.

Practise saying it · 60 s. No recording, just a timer

Explain the one-letter-change BFS.

Say your answer out loud, then check which of these points you covered:

  • Words as nodes
  • Generate neighbours by position
  • BFS for shortest chain

Deep dive

Grouping words by patterns like 'c*t' is another fast way to find neighbours.

Bidirectional BFS meets in the middle and explores far fewer words on big lists.

Remove words from the allowed set when queued so they are not queued twice.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
from collections import deque
from string import ascii_lowercase


def chain_length(start: str, target: str, allowed: list[str]) -> int:
    left = set(allowed)
    if target not in left:
        return 0
    queue = deque([(start, 1)])
    left.discard(start)
    while queue:
        word, length = queue.popleft()
        if word == target:
            return length
        for i in range(len(word)):
            for ch in ascii_lowercase:
                cand = word[:i] + ch + word[i + 1:]
                if cand in left:
                    left.remove(cand)
                    queue.append((cand, length + 1))
    return 0

Common mistakes

  • Comparing every pair of words to build the graph, which is O(N²·L).
  • Returning the number of changes when the question asks for the number of words.

Senior take & follow-ups

Say whether you count words or changes before you start.

Follow-up questions

Think of your answer first, then open the hint.

  1. How would you return the chain itself?

    Show hint

    Record parents during BFS and walk back.

  2. What if all shortest chains are needed?

    Show hint

    BFS to build a layered parent map, then backtrack through it.

What each operation costs: Breadth First Search · Depth First Search · Topological Sort · Dijkstra Algorithm

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.