Dictionary Word Transformation Path

Problem Overview

You are given:

• a start word
• a target word
• a dictionary of allowed words

Determine whether the words can be connected by a valid transformation sequence.

Each step in the sequence must move from the current word to another word of the same length. The interviewer usually starts with the standard one-character version, then adds a follow-up where a move may change one or two characters.

This is essentially a Word Ladder style graph problem:

• each word is a node
• an edge exists when two words differ by an allowed number of character positions
• the task is to search for a path from start to target

Assume:

• all usable words have the same length
• start and target are lowercase strings
• the dictionary may contain duplicates; treat it as a set
• start does not need to be in the dictionary
• target should still be considered a valid destination even if it is not already in the dictionary
• words should not be revisited once already explored

Part 1: Reachability With One-Character Transforms

Problem Statement

Implement:

def has_path_one_edit(start: str, target: str, words: list[str]) -> bool:
    ...

Return True if there exists a sequence from start to target such that:

• every step changes exactly one character
• every intermediate word is in the dictionary
• target may be used as the final word even if it is not in the dictionary

Example

start = "hit"
target = "cog"
words = ["hot", "dot", "dog", "lot", "log", "cog"]

has_path_one_edit(start, target, words)  # True

One valid path is:

hit -> hot -> dot -> dog -> cog

Part 2: Reachability With One- Or Two-Character Transforms

Problem Statement

Now extend the rule:

• a valid move may change either exactly one character or exactly two characters

Implement:

def has_path_one_or_two_edits(start: str, target: str, words: list[str]) -> bool:
    ...

Example

start = "code"
target = "math"
words = ["coda", "cada", "mata"]

has_path_one_or_two_edits(start, target, words)  # True

One valid path is:

code -> coda -> cada -> mata -> math

The key jump is:

cada -> mata

which changes two character positions.

Part 3: Return An Actual Path

Problem Statement

Now return one shortest valid path instead of only a boolean.

Implement:

def shortest_path_one_or_two_edits(
    start: str,
    target: str,
    words: list[str],
) -> list[str]:
    ...

Return:

• a shortest valid transformation sequence from start to target, inclusive
• [] if no path exists

Example

start = "code"
target = "math"
words = ["coda", "cada", "mata"]

shortest_path_one_or_two_edits(start, target, words)
# ["code", "cada", "mata", "math"]

The shorter path is valid because code -> cada changes two character positions, which is allowed in this follow-up.

Discussion Points

Interviewers often use this question to check whether the candidate can:

• model the problem as a graph instead of getting stuck on string manipulation
• explain when DFS is enough versus when BFS is the better choice
• handle the two-character follow-up without overcomplicating the solution too early
• reason about neighbor-generation tradeoffs

Good follow-up discussion:

• DFS is sufficient if the task is only "does any path exist?"
• BFS is better if the task changes to "find the shortest path"
• for large dictionaries, precomputed neighbor indexes can help Part 1
• Part 2 is less friendly to the standard Word Ladder wildcard optimization, so a direct Hamming-distance scan is often the cleanest baseline answer