Dictionary Word Transformation Path

medium

CodingOld question · last reported Jul 2025

Word Dictionary Transformation Chains

Coding

Problem Overview

You receive the following inputs:

a start word
a target word
a collection of permitted dictionary words

Decide whether a legal sequence of word changes can link the first word to the second.

A transition must go from the current word to a same-length word. Typically, the initial version permits changing one character, followed by a variant that permits changing either one or two characters.

This can be viewed as a Word Ladder graph:

every word represents a vertex
two vertices are connected when their character differences meet the permitted limit
search the graph for a route between start and target

Use these assumptions:

every eligible word has identical length
both start and target contain lowercase letters
repeated dictionary entries have no additional effect, since the dictionary is treated as a set
start is not required to appear in the dictionary
target remains an allowed final destination even when absent from the dictionary
do not explore a word again after it has been visited

Problem Statement

Implement:

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

Produce True when a transformation chain exists from start to target with these properties:

each transition modifies precisely one character
all words between the endpoints must belong to the dictionary
target is allowed as the last word even when the dictionary does not contain it

Example

start = "cold"
target = "warm"
words = ["cord", "card", "ward"]

solve(start, target, words, 1) # True

A possible sequence is:

cold -> cord -> card -> ward -> warm

Each neighboring pair differs at exactly one position, and only the endpoint warm is allowed to be outside the dictionary.

Problem Statement

Expand the movement condition as follows:

one move may alter exactly one character or exactly two characters

Implement:

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

Example

start = "bake"
target = "torn"
words = ["bore", "tone"]

solve(start, target, words, 2) # True

One valid chain is:

bake -> bore -> tone -> torn

For example, this transition is permitted:

bore -> tone

It changes two character locations.

Problem Statement

Instead of returning only a boolean, return a shortest legal chain.

Implement:

def solve(start: str, target: str, words: list[str], part: int) -> list[str]:
    ...

Return:

one minimum-length valid transformation sequence, including both start and target
[] when no valid sequence can be formed

Example

start = "bake"
target = "torn"
words = ["bore", "tone"]

solve(start, target, words, 3)
# ["bake", "bore", "torn"]

This shorter route is legal because both bake -> bore and bore -> torn modify two positions, which this version permits.

BackBack to problems

Dictionary Word Transformation Path

medium

CodingOld question · last reported Jul 2025

Word Dictionary Transformation Chains

Coding

Problem Overview

You receive the following inputs:

a start word
a target word
a collection of permitted dictionary words

Decide whether a legal sequence of word changes can link the first word to the second.

This can be viewed as a Word Ladder graph:

every word represents a vertex
two vertices are connected when their character differences meet the permitted limit
search the graph for a route between start and target

Use these assumptions:

every eligible word has identical length
both start and target contain lowercase letters
repeated dictionary entries have no additional effect, since the dictionary is treated as a set
start is not required to appear in the dictionary
target remains an allowed final destination even when absent from the dictionary
do not explore a word again after it has been visited

Problem Statement

Implement:

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

Produce True when a transformation chain exists from start to target with these properties:

each transition modifies precisely one character
all words between the endpoints must belong to the dictionary
target is allowed as the last word even when the dictionary does not contain it

Example

start = "cold"
target = "warm"
words = ["cord", "card", "ward"]

solve(start, target, words, 1) # True

A possible sequence is:

cold -> cord -> card -> ward -> warm

Each neighboring pair differs at exactly one position, and only the endpoint warm is allowed to be outside the dictionary.

Problem Statement

Expand the movement condition as follows:

one move may alter exactly one character or exactly two characters

Implement:

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

Example

start = "bake"
target = "torn"
words = ["bore", "tone"]

solve(start, target, words, 2) # True

One valid chain is:

bake -> bore -> tone -> torn

For example, this transition is permitted:

bore -> tone

It changes two character locations.

Problem Statement

Instead of returning only a boolean, return a shortest legal chain.

Implement:

def solve(start: str, target: str, words: list[str], part: int) -> list[str]:
    ...

Return:

one minimum-length valid transformation sequence, including both start and target
[] when no valid sequence can be formed

Example

start = "bake"
target = "torn"
words = ["bore", "tone"]

solve(start, target, words, 3)
# ["bake", "bore", "torn"]

This shorter route is legal because both bake -> bore and bore -> torn modify two positions, which this version permits.

Dictionary Word Transformation Path

Word Dictionary Transformation Chains

Problem Overview

Part 1: One-Character Reachability

Problem Statement

Example

Part 2: Reachability Using One or Two Character Changes

Problem Statement

Example

Part 3: Produce a Concrete Path

Problem Statement

Example

Dictionary Word Transformation Path

Word Dictionary Transformation Chains

Problem Overview

Part 1: One-Character Reachability

Problem Statement

Example

Part 2: Reachability Using One or Two Character Changes

Problem Statement

Example

Part 3: Produce a Concrete Path

Problem Statement

Example