Word Ladder

PracticeNeetCode ↗LeetCode ↗

Given a beginWord, an endWord, and a wordList, return the length of the shortest transformation sequence from beginWord to endWord, changing exactly one letter at a time, where every intermediate word must appear in wordList. Return 0 if no such sequence exists.

Example

Key Pointers

• This is shortest-path-in-an-unweighted-graph — BFS is the right tool, where each word is a node and an edge connects two words differing by exactly one letter.
• Generating neighbors by trying all 26 letters at each position keeps neighbor generation independent of how large the word list is.
• Removing a word from the set the moment it's used as a neighbor prevents the BFS from revisiting it and blowing up.

Step-by-Step Analysis

1. Put wordList into a set for O(1) lookups; if endWord isn't in it, return 0 immediately.
2. BFS from beginWord, tracking the transformation length (starting at 1).
3. At each word, try changing every position to every letter a–z; if the result is in the word set, it's a valid neighbor — remove it from the set and enqueue it with length + 1.
4. The moment endWord is generated as a neighbor, return the current length + 1. If the queue empties first, return 0.

Complexity

Time: O(n · 26 · L), where n is the word count and L is the word length — Space: O(n · L)

Code

from collections import deque

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

    queue = deque([(beginWord, 1)])
    word_set.discard(beginWord)

    while queue:
        word, length = queue.popleft()
        if word == endWord:
            return length

        for i in range(len(word)):
            for ch in "abcdefghijklmnopqrstuvwxyz":
                next_word = word[:i] + ch + word[i + 1:]
                if next_word in word_set:
                    word_set.remove(next_word)
                    queue.append((next_word, length + 1))

    return 0

Code Explanation

How the solution above works, piece by piece.

1. Put the word list in a set for O(1) lookups; if endWord isn't in it, no ladder exists.
2. BFS from beginWord, storing each word with its ladder length.
3. For each word, try changing every position to every letter a–z. Any result still in the set is a neighbour.
4. Remove neighbours from the set as they're queued; this acts as the visited set and stops words being queued twice.
5. The first time endWord is popped, its length is the shortest. O(N · L · 26) for N words of length L.

Visual Walkthrough

Running it on beginWord = "hit", endWord = "cog":

Video Explanation

NeetCode — Breadth First Search, LeetCode 127