Word Ladder Leetcode Problem 127 [Python Solution]

The Word Ladder problem is a challenging one that falls under the “Hard” category of LeetCode questions.

It’s related to graphs and is often asked by tech giants like Google.

Problem Statement:

You are given a transformation sequence from a beginning word to an end word using a dictionary of words.

A valid sequence consists of words that:

1. Differ by a single character.
2. Each word in the sequence is in the provided word list.

Your task is to find and return the number of words in the shortest transformation sequence from the beginning word to the end word.

If no such sequence exists, return 0.

Understanding the Constraints

Before we dive into the solution, let’s understand the constraints of the problem:

• The length of the beginWord is between 1 and 10.
• The length of the endWord is the same as beginWord.
• The length of the wordList can be as large as 5000.
• All words consist of lowercase English letters.
• The beginWord is not necessarily in the wordList.
• All words in the wordList are unique.

Efficient Python Code Solution

View on GitHub ➹
import collections
from collections import deque
from typing import List

def ladderLength(beginWord: str, endWord: str, wordList: List[str]) -> int:
    if endWord not in wordList:
        return 0

    # Build the adjacency list
    neighbors = collections.defaultdict(list)
    wordList.append(beginWord)
    for word in wordList:
        for j in range(len(word)):
            pattern = word[:j] + "*" + word[j + 1 :]
            neighbors[pattern].append(word)

    # Initialize data structures for BFS
    visited = set([beginWord])
    queue = deque([beginWord])
    path_length = 1

    while queue:
        for i in range(len(queue)):
            word = queue.popleft()
            if word == endWord:
                return path_length
            for j in range(len(word)):
                pattern = word[:j] + "*" + word[j + 1 :]
                for neighbor in neighbors[pattern]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
        path_length += 1

    return 0