Word Morph Chain
HardGraphs
Problem
In a word puzzle you turn start into goal one letter at a time. Each move replaces exactly one letter, and every word you create along the way (including goal) must appear in the dictionary words. start itself does not need to be in the dictionary.
Return the number of words in the shortest chain from start to goal, counting both ends, or 0 if no chain exists.
Example 1
- Input:
- start = "cold", goal = "warm", words = ["cord","card","ward","warm","worm","word"]
- Output:
- 5
cold → cord → card → ward → warm. The words differ in four positions, so no chain can be shorter.
Example 2
- Input:
- start = "cold", goal = "warm", words = ["cord","card","ward","worm","word"]
- Output:
- 0
The goal is not in the dictionary.
Constraints
- 1 ≤ start.length ≤ 10
- goal.length = start.length and start ≠ goal
- 1 ≤ words.length ≤ 5000
- All words have the same length and consist of lowercase English letters.
Hint
Show the first hint
Treat every word as a node, with an edge between words that differ in exactly one position.
Walkthrough
How to approach it
01Clarify before coding
- Does the count include start and goal? Yes, it counts words in the chain, so a single move gives 2.
- Must goal be in the dictionary? Yes; if it is not, the answer is 0.
- Are all words the same length and lowercase? Yes.
02Brute force
Build the explicit graph by comparing every pair of dictionary words, then BFS.
Cost: O(N² · L) to build: 25 million pair comparisons of length 10 at N = 5000, before the search even starts.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.