Word Ladder — Shortest Transformation Length

DiffPush Tier Graphs · Traversal Problems O(n * m^2) · O(n * m)

The One-Toggle Relay Upgrade Path

A network operations team maintains firmware configs as fixed-length strings, and a change window allows flipping exactly one character slot per deploy. Every intermediate config must come from the approved repository. Given a starting config and a target, the change board wants the minimum number of deploys' worth of configs in a legal upgrade path — or proof that the target is unreachable under the one-toggle rule.

Input: Strings beginWord and endWord of equal length, and a list wordList of approved words.

Output: Return how many words a valid chain contains from beginWord through to endWord (endpoints included), or 0 when no chain exists.

Constraints

1 <= beginWord.length <= 10
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
All words consist of lowercase English letters
beginWord does not need to be in wordList; endWord must be for a path to exist

Examples

Example 1

Input: {"beginWord":"hit","endWord":"cog","wordList":["hot","dot","dog","lot","log","cog"]}
Output: 5
hit -> hot -> dot -> dog -> cog is the shortest five-word ladder.

Example 2

Input: {"beginWord":"hit","endWord":"cog","wordList":["hot","dot","dog","lot","log"]}
Output: 0
The target config was never approved, so no ladder can terminate on it.

Solve this in your browser →

Also on LeetCode ↗