Shortest Transformation Sequence

Given a starting word, an ending word, and a dictionary of valid words, find the minimum number of transformations to change the starting word into the ending word by changing one letter at a time, where each intermediate word must exist in the dictionary.

GraphsBreadth-First SearchString ManipulationShortest PathDictionary

Problem Statement

You are given a starting word startWord, an ending word endWord, and a list of valid words wordList. Your task is to find the length of the shortest transformation sequence from startWord to endWord such that only one letter can be changed at a time and each transformed word (including the startWord but excluding the endWord) must be present in the wordList. If no such sequence exists, return 0. Assume that all words have the same length and contain only lowercase alphabetic characters.

Example 1

Input: {'startWord': 'cat', 'endWord': 'dog', 'wordList': ['cat', 'cot', 'cog', 'dog', 'tot', 'bog']}

Output: 4

One possible shortest transformation sequence is 'cat' -> 'cot' -> 'cog' -> 'dog', which has a length of 4.

Example 2

Input: {'startWord': 'hat', 'endWord': 'cow', 'wordList': ['hat', 'hot', 'dot', 'dog', 'lot', 'log', 'cog', 'cow']}

Output: 5

One possible shortest transformation sequence is 'hat' -> 'hot' -> 'dot' -> 'dog' -> 'cog' -> 'cow', which has a length of 6.

Constraints

-All words in `wordList` have the same length.
-`startWord` and `endWord` have the same length.
-All words contain only lowercase English letters.
-1 <= Length of `startWord`, `endWord`, and words in `wordList` <= 10
-1 <= Number of words in `wordList` <= 500

Brute Force Approach

A brute-force approach would involve generating all possible word sequences starting from startWord, changing one letter at a time, and checking if each intermediate word is in wordList. This is similar to exploring every possible path in a maze until you find the exit, without remembering where you've already been. You would generate all possible transformations until you reach endWord or exhaust all possibilities.

TimeO((26^L)^N)

SpaceO(N)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem