LeetCode 127: Word Ladder

Problem Restatement

We are given:

We may transform one word into another by changing exactly one character.

Every transformed word must exist in wordList.

We need to return the number of words in the shortest transformation sequence from beginWord to endWord.

If no valid sequence exists, return 0.

Examples

Example 1:

beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]

One shortest sequence is:

hit -> hot -> dot -> dog -> cog

Length:

5

Another shortest sequence also exists:

hit -> hot -> lot -> log -> cog

The answer is still 5 because we only need the shortest length.

Example 2:

beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log"]

Output:

0

Because "cog" does not exist in wordList.

Input and Output

Function shape:

class Solution:
    def ladderLength(
        self,
        beginWord: str,
        endWord: str,
        wordList: list[str],
    ) -> int:
        ...

Graph Interpretation

Think of each word as a node in a graph.

Two words are connected if they differ by exactly one character.

For example:

hot -> dot
hot -> lot
dot -> dog
lot -> log
dog -> cog
log -> cog

The problem becomes:

Find the shortest path from beginWord to endWord.

Because every edge has equal weight, BFS is the correct algorithm.

Why BFS Works

Breadth-first search explores nodes level by level.

Level meaning:

The first time BFS reaches endWord, we know that path is shortest.

That is the main reason BFS is used here instead of DFS.

Brute Force Idea

A brute force solution could try every possible transformation recursively.

That becomes extremely expensive because the number of paths grows rapidly.

Instead, BFS avoids exploring long unnecessary paths.

As soon as we reach endWord, we stop immediately.

Key Insight

For each word, we can generate all possible one-letter transformations.

Suppose the current word is:

"hot"

Possible one-letter mutations include:

aot
bot
cot
...
hat
hbt
...
hoa
hob
...

Most are invalid.

We only keep words that exist in wordList.

To make lookup fast, store all dictionary words in a set:

word_set = set(wordList)

Set lookup is approximately O(1).

Algorithm

First, convert the dictionary into a set.

If endWord is missing, return 0.

Then start BFS from beginWord.

The queue stores:

(word, distance)

For every word:

1. Try changing each character position.
2. Replace it with every letter from 'a' to 'z'.
3. If the generated word exists in the set:
   • add it to the queue
   • remove it from the set
4. If the generated word equals endWord, return the distance immediately.

Removing visited words is important.

Without it, BFS may revisit the same word many times.

Correctness

BFS processes words in increasing order of transformation length.

At distance 1, it visits all words reachable in one change.

At distance 2, it visits all words reachable in two changes.

This continues until endWord is found.

Because BFS explores shorter paths before longer ones, the first time we reach endWord must correspond to the shortest possible sequence.

The algorithm only moves to valid dictionary words differing by one character, so every generated path is valid.

Therefore, the returned distance is exactly the shortest transformation length.

Complexity

Let:

For every visited word:

• we try m positions
• for each position, we try 26 letters

So the total work is approximately:

O(n * m * 26)

Simplified:

O(n * m)

Space usage:

The queue and set may both contain many words.

Implementation

from collections import deque

class Solution:
    def ladderLength(
        self,
        beginWord: str,
        endWord: str,
        wordList: list[str],
    ) -> int:
        word_set = set(wordList)

        if endWord not in word_set:
            return 0

        queue = deque([(beginWord, 1)])

        if beginWord in word_set:
            word_set.remove(beginWord)

        while queue:
            word, steps = queue.popleft()
            chars = list(word)

            for i in range(len(chars)):
                original = chars[i]

                for code in range(ord("a"), ord("z") + 1):
                    chars[i] = chr(code)
                    next_word = "".join(chars)

                    if next_word == endWord:
                        return steps + 1

                    if next_word not in word_set:
                        continue

                    word_set.remove(next_word)
                    queue.append((next_word, steps + 1))

                chars[i] = original

        return 0

Code Explanation

We first convert the dictionary into a set:

word_set = set(wordList)

This makes lookup fast.

Then we handle the impossible case:

if endWord not in word_set:
    return 0

The BFS queue stores:

(word, steps)

Example:

("hit", 1)

means:

“We are currently at "hit" and the sequence length is 1.”

For each character position:

for i in range(len(chars)):

we try replacing it with all letters:

for code in range(ord("a"), ord("z") + 1):

Then we rebuild the candidate word:

next_word = "".join(chars)

If it matches endWord, we immediately return:

steps + 1

Otherwise, if it exists in the dictionary:

if next_word in word_set:

we:

1. mark it visited
2. push it into the queue

word_set.remove(next_word)
queue.append((next_word, steps + 1))

Removing visited words prevents repeated processing.

Testing

def run_tests():
    s = Solution()

    assert s.ladderLength(
        "hit",
        "cog",
        ["hot", "dot", "dog", "lot", "log", "cog"],
    ) == 5

    assert s.ladderLength(
        "hit",
        "cog",
        ["hot", "dot", "dog", "lot", "log"],
    ) == 0

    assert s.ladderLength(
        "a",
        "c",
        ["a", "b", "c"],
    ) == 2

    assert s.ladderLength(
        "hot",
        "dog",
        ["hot", "dog"],
    ) == 0

    assert s.ladderLength(
        "red",
        "tax",
        ["ted", "tex", "red", "tax", "tad", "den", "rex", "pee"],
    ) == 4

    print("all tests passed")

run_tests()

Test meaning: