Word Ladder

Difficulty: Hard Source: NeetCode

Problem

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

• Every adjacent pair of words differs by a single letter.
• Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
• sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example 1: Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 (sequence: hit → hot → dot → dog → cog)

Example 2: Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: 0 (cog not in wordList)

Constraints:

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• All words have the same length and consist of lowercase English letters

Prerequisites

Before attempting this problem, you should be comfortable with:

• BFS for shortest path — minimum transformation steps = shortest path in a graph
• State-space search — each word is a node; edges connect words differing by one letter
• Set lookups — converting wordList to a set for O(1) neighbor checking

1. Brute Force BFS (Generate all neighbors by comparison)

Intuition

BFS from beginWord. At each step, find all words in wordList that differ by exactly one letter from the current word. This is correct but O(N * L) per node for neighbor generation, where N = wordList size and L = word length.

Algorithm

1. Convert wordList to a set for fast lookup.
2. BFS with (current_word, steps). Start at (beginWord, 1).
3. For each current word, check every word in the word set that differs by one letter.
4. Return steps when endWord is reached.

Solution

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

    def neighbors(word):
        result = []
        for candidate in word_set:
            diff = sum(a != b for a, b in zip(word, candidate))
            if diff == 1:
                result.append(candidate)
        return result

    visited = {beginWord}
    queue = deque([(beginWord, 1)])

    while queue:
        word, steps = queue.popleft()
        for neighbor in neighbors(word):
            if neighbor == endWord:
                return steps + 1
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, steps + 1))

    return 0


print(ladderLength("hit", "cog", ["hot","dot","dog","lot","log","cog"]))  # 5
print(ladderLength("hit", "cog", ["hot","dot","dog","lot","log"]))         # 0

Complexity

• Time: O(N² * L) — for each of N nodes, compare against all N words
• Space: O(N)

2. BFS with Letter-by-Letter Neighbor Generation

Intuition

Instead of comparing every word in the list, generate candidate neighbors by replacing each letter of the current word with 'a' through 'z' and checking if the result is in the word set. This generates at most L * 26 candidates per word — much faster than scanning all N words.

Algorithm

1. Convert wordList to a set.
2. BFS from beginWord. For each word, generate neighbors by replacing each of L positions with each of 26 letters.
3. Keep only neighbors that are in word_set and not yet visited.
4. Return step count when endWord is reached, or 0 if queue empties.

Solution

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

    visited = {beginWord}
    queue = deque([(beginWord, 1)])

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

        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                if c == word[i]:
                    continue
                candidate = word[:i] + c + word[i+1:]
                if candidate in word_set and candidate not in visited:
                    visited.add(candidate)
                    queue.append((candidate, steps + 1))

    return 0


print(ladderLength("hit", "cog", ["hot","dot","dog","lot","log","cog"]))  # 5
print(ladderLength("hit", "cog", ["hot","dot","dog","lot","log"]))         # 0
print(ladderLength("a", "c", ["a","b","c"]))                               # 2

Complexity

• Time: O(N * L * 26) — for each of N words in the BFS, try L positions × 26 letters
• Space: O(N * L) for visited set and queue

3. Bidirectional BFS

Intuition

Same as the Open the Lock trick: expand from both beginWord and endWord simultaneously. When the two frontiers collide, we’ve found the shortest path. This cuts the search space roughly in half in practice.

Solution

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

    def get_neighbors(word):
        result = []
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                if c != word[i]:
                    candidate = word[:i] + c + word[i+1:]
                    if candidate in word_set:
                        result.append(candidate)
        return result

    begin_visited = {beginWord: 1}
    end_visited = {endWord: 1}
    begin_queue = deque([beginWord])
    end_queue = deque([endWord])

    while begin_queue and end_queue:
        # Expand begin frontier
        word = begin_queue.popleft()
        steps = begin_visited[word]
        for neighbor in get_neighbors(word):
            if neighbor in end_visited:
                return steps + end_visited[neighbor]
            if neighbor not in begin_visited:
                begin_visited[neighbor] = steps + 1
                begin_queue.append(neighbor)

        # Expand end frontier
        word = end_queue.popleft()
        steps = end_visited[word]
        for neighbor in get_neighbors(word):
            if neighbor in begin_visited:
                return steps + begin_visited[neighbor]
            if neighbor not in end_visited:
                end_visited[neighbor] = steps + 1
                end_queue.append(neighbor)

    return 0


print(ladderLength("hit", "cog", ["hot","dot","dog","lot","log","cog"]))  # 5
print(ladderLength("hit", "cog", ["hot","dot","dog","lot","log"]))         # 0

Complexity

• Time: O(N * L * 26) with smaller constant due to bidirectional search
• Space: O(N * L)

Common Pitfalls

Checking endWord in wordList. Unlike beginWord, endWord must be in the word list. If it’s not, immediately return 0.

Counting the begin word. The problem asks for the number of words in the sequence, not the number of steps. The sequence hit → hot → dot → dog → cog has 5 words but 4 steps. Start BFS with steps = 1 (counting the starting word) or remember to add 1 at the end.

Marking visited before enqueuing. Add words to visited when enqueuing, not when dequeuing. Otherwise, the same word can be enqueued multiple times from different paths, causing redundant work or incorrect results.