Word Ladder Length
Hard
1
24.1% Acceptance
Welcome to the Word Ladder Lab! In this lab, you'll implement the word_ladder
function. Your task is to calculate the length of the shortest transformation sequence from a beginWord
to an endWord
, using only words from a given wordList
. Each step in the transformation can change just one letter of the word, and each intermediate word must be in the wordList
.
Function Signature:
def word_ladder(beginWord: str, endWord: str, wordList: List[str]) -> int:
Examples:
-
Basic Transformation:
- Input:
beginWord = "and"
,endWord = "ant"
,wordList = ["add", "aid", "and", "ant", "any", ...]
- Output:
1
- Explanation: The shortest transformation is "and" -> "ant".
- Input:
-
Complex Transformation:
- Input:
beginWord = "phone"
,endWord = "phase"
,wordList = ["phone", "phane", "plane", "phase", "prase", ...]
- Output:
X
(WhereX
is the length of the shortest transformation sequence) - Explanation: One possible transformation sequence is "phone" -> "phane" -> "plane" -> "prane" -> "prase" -> "phase".
- Input:
Your implementation should efficiently find the shortest sequence. Good luck!