Given two words, beginWord and endWord, and a dictionary of words wordList, find the length of the shortest transformation sequence from beginWord to endWord such that:

  1. Only one letter can be changed at a time.
  2. Each transformed word (including the endWord) must exist in the word list.
  3. If there is no such transformation sequence, return -1.

Function Signature:

from typing import List

def ladder_length(beginWord: str, endWord: str, wordList: List[str]) -> int:
    """
    Find the length of the shortest transformation sequence from beginWord to endWord.

    Parameters:
    - beginWord: The starting word (string).
    - endWord: The target word (string).
    - wordList: A list of words (strings).

    Returns:
    - int: The length of the shortest transformation sequence, or -1 if not possible.
    """
    # Your code here

Example:

result = ladder_length("abc", "bca", ["aba", "bba", "bca", "aaa"])
print(result) 
assert result == 3
# Explanation: The shortest transformation sequence is "abc" -> "aba" -> "bba" -> "bca"

result = ladder_length("abc", "abc", ["abc"])
print(result) 
assert result == 0
# Explanation: The endWord is in wordList. The beginWord is equal to the endWord. Transformation length is 0. 

result = ladder_length("abc", "bca", [""])
print(result) 
assert result == -1
# Explanation: The word list is empty. No transformation is possible.

result = ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])
print(result)
assert result == 4
# Explanation: The shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> "cog".

result = ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log"])
print(result)
assert result == -1
# Explanation: There is no transformation sequence from "hit" to "cog" using the given wordList.

Note:

  • All words have the same length.
  • All words in the word list are lowercase.
  • The transformation sequence must start from beginWord and end at endWord.
  • Only one letter can be changed at a time.
  • Each transformed word (including the endWord) must exist in the word list.

Instructions:

  • Write the ladder_length function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊