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:

  1. Basic Transformation:

    • Input: beginWord = "and", endWord = "ant", wordList = ["add", "aid", "and", "ant", "any", ...]
    • Output: 1
    • Explanation: The shortest transformation is "and" -> "ant".
  2. Complex Transformation:

    • Input: beginWord = "phone", endWord = "phase", wordList = ["phone", "phane", "plane", "phase", "prase", ...]
    • Output: X (Where X is the length of the shortest transformation sequence)
    • Explanation: One possible transformation sequence is "phone" -> "phane" -> "plane" -> "prane" -> "prase" -> "phase".

Your implementation should efficiently find the shortest sequence. Good luck!