Word Ladder

Problem

Given two words and a dictionary, find the length of the shortest transformation sequence from beginWord to endWord, such that only one letter can be changed at a time and each intermediate word must exist in the word list.

Approach

BFS level-by-level. At each level, for every word generate all possible one-character mutations and check if they exist in the remaining word set.

When to Use

BFS for shortest transformation sequence — "minimum edits", "fewest steps to transform X into Y", unweighted shortest path in an implicit graph. Keywords: "word ladder", "gene mutation", "lock combination".

Complexity

Time	O(n * m^2) where n = |word_list|, m = word length
Space	O(n * m)

Implementation

SolutionTestsChallenge

word_ladder

Shortest transformation sequence from beginWord to endWord.

Problem

Given two words and a dictionary, find the length of the shortest transformation sequence from beginWord to endWord, such that only one letter can be changed at a time and each intermediate word must exist in the word list.

Approach

BFS level-by-level. At each level, for every word generate all possible one-character mutations and check if they exist in the remaining word set.

When to use

BFS for shortest transformation sequence — "minimum edits", "fewest steps to transform X into Y", unweighted shortest path in an implicit graph. Keywords: "word ladder", "gene mutation", "lock combination".

Complexity

Time: O(n * m^2) where n = |word_list|, m = word length (m patterns per word, each pattern is O(m) to build) Space: O(n * m)

ladder_length

ladder_length(
    begin_word: str, end_word: str, word_list: list[str]
) -> int

Return the number of words in the shortest transformation sequence.

Returns 0 if no such sequence exists. The count includes both begin_word and end_word.

ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]) 5

Source code in src/algo/graphs/word_ladder.py

def ladder_length(begin_word: str, end_word: str, word_list: list[str]) -> int:
    """Return the number of words in the shortest transformation sequence.

    Returns 0 if no such sequence exists. The count includes both
    begin_word and end_word.

    >>> ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])
    5
    """
    word_set = set(word_list)
    if end_word not in word_set:
        return 0

    queue: deque[str] = deque([begin_word])
    visited: set[str] = {begin_word}
    level = 1

    while queue:
        for _ in range(len(queue)):
            word = queue.popleft()
            if word == end_word:
                return level
            for neighbor in _neighbors(word, word_set, visited):
                visited.add(neighbor)
                queue.append(neighbor)
        level += 1

    return 0

tests/graphs/test_word_ladder.py

"""Tests for word ladder (BFS shortest transformation)."""

from algo.graphs.word_ladder import ladder_length


class TestLadderLength:
    def test_basic(self) -> None:
        words = ["hot", "dot", "dog", "lot", "log", "cog"]
        assert ladder_length("hit", "cog", words) == 5

    def test_no_path(self) -> None:
        words = ["hot", "dot", "dog", "lot", "log"]
        assert ladder_length("hit", "cog", words) == 0

    def test_end_not_in_list(self) -> None:
        assert ladder_length("hit", "cog", ["hot"]) == 0

    def test_one_step(self) -> None:
        assert ladder_length("hot", "dot", ["dot"]) == 2

    def test_already_equal(self) -> None:
        assert ladder_length("abc", "abc", ["abc"]) == 1

    def test_empty_word_list(self) -> None:
        assert ladder_length("a", "b", []) == 0

Implement it yourself

Run: just challenge graphs word_ladder

Then implement the functions to make all tests pass. Use just study graphs for watch mode.

Reveal Solution

word_ladder

Shortest transformation sequence from beginWord to endWord.

Problem

Given two words and a dictionary, find the length of the shortest transformation sequence from beginWord to endWord, such that only one letter can be changed at a time and each intermediate word must exist in the word list.

Approach

BFS level-by-level. At each level, for every word generate all possible one-character mutations and check if they exist in the remaining word set.

When to use

BFS for shortest transformation sequence — "minimum edits", "fewest steps to transform X into Y", unweighted shortest path in an implicit graph. Keywords: "word ladder", "gene mutation", "lock combination".

Complexity

Time: O(n * m^2) where n = |word_list|, m = word length (m patterns per word, each pattern is O(m) to build) Space: O(n * m)

ladder_length

ladder_length(
    begin_word: str, end_word: str, word_list: list[str]
) -> int

Return the number of words in the shortest transformation sequence.

Returns 0 if no such sequence exists. The count includes both begin_word and end_word.

ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]) 5

Source code in src/algo/graphs/word_ladder.py

def ladder_length(begin_word: str, end_word: str, word_list: list[str]) -> int:
    """Return the number of words in the shortest transformation sequence.

    Returns 0 if no such sequence exists. The count includes both
    begin_word and end_word.

    >>> ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])
    5
    """
    word_set = set(word_list)
    if end_word not in word_set:
        return 0

    queue: deque[str] = deque([begin_word])
    visited: set[str] = {begin_word}
    level = 1

    while queue:
        for _ in range(len(queue)):
            word = queue.popleft()
            if word == end_word:
                return level
            for neighbor in _neighbors(word, word_set, visited):
                visited.add(neighbor)
                queue.append(neighbor)
        level += 1

    return 0