Word Ladder
Welcome to the Word Ladder challenge! In this fun exercise, it's all about creating word transformations. Imagine you have two words, and you want to transform the first word into the second word by altering one letter at a time, where each intermediate word must be a valid word from a given word dictionary.
The goal of this challenge is to find the shortest transformation sequence from the word begin to the word end, given a list of valid words (word_list). If no such transformation is possible, the function should return zero.
A Word Ladder should satisfy the following constraints:
- The
beginword is not in theword_list(it's the starting point). - The
endword must be in theword_list. - Each intermediate word in the transformation must be in the
word_list. - Only one letter can be changed at a time.
- The function should return the total number of words in the transformation sequence (including
beginandend).
Your task is to implement the function word_ladder(begin: str, end: str, word_list: List[str]) -> int.
Example:
word_ladder("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])
Output: 5
Transformation path in the sequence: hit -> hot -> dot -> dog -> cog (5 words total)
word_ladder("hit", "cog", ["hot", "dot", "dog", "lot", "log"])
Output: 0
No valid transformation sequence exists that leads to cog because cog is not in the word list.
Good luck, and may the ladder of words reach your destination!
Inputs
Arg 1:
"hit"Arg 2:
"cog"Arg 3:
["hot","dot","dog","lot","log","cog"]Expected Output
5Actual Output