Here’s a solution to the “Word Ladder Transformation” problem:

from typing import List
from collections import deque

def ladder_length(beginWord: str, endWord: str, wordList: List[str]) -> int:
    # Convert the wordList to a set for faster lookup
    wordSet = set(wordList)

    # Check if the endWord is not in the wordList, return 0
    if endWord not in wordSet:
        return -1

    # Use a queue for BFS and initialize the queue with the beginWord
    queue = deque([(beginWord, 0)])

    while queue:
        currentWord, transformations = queue.popleft()

        # Check if the currentWord is the endWord
        if currentWord == endWord:
            return transformations

        # Explore neighbors by changing one letter at a time
        for i in range(len(currentWord)):
            for char in 'abcdefghijklmnopqrstuvwxyz':
                neighbor = currentWord[:i] + char + currentWord[i + 1:]

                # Check if the neighbor is in the wordSet
                if neighbor in wordSet:
                    wordSet.remove(neighbor)  # Mark the word as visited
                    queue.append((neighbor, transformations + 1))

    # If no transformation sequence is found
    return -1

# Example usage:
result = ladder_length("abc", "bca", ["aba", "bba", "bca", "aaa"])
print(result) 
assert result == 3

result = ladder_length("abc", "abc", ["abc"])
print(result) 
assert result == 0

result = ladder_length("abc", "bca", [""])
print(result) 
assert result == -1

result = ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])
print(result)
assert result == 4

result = ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log"])
print(result)
assert result == -1

Time Complexity:

The time complexity is O(N * M), where N is the number of words in the wordList and M is the length of each word. In the worst case, we visit all words in the wordList, and for each word, we iterate through all possible transformations.

Space Complexity:

The time complexity is O(N * M), where N is the number of words in the wordList and M is the length of each word. In the worst case, we visit all words in the wordList, and for each word, we iterate through all possible transformations.