HardHash TableStringBreadth-First Search

Word Ladder

1 approach, code in every language

You are given two words, beginWord and endWord, together with a dictionary wordList.

A transformation sequence starts at beginWord and ends at endWord. At each step you may change exactly one letter, and every word produced after the first step must appear in wordList. Note that beginWord itself does not need to be in wordList.

Return the number of words in the shortest transformation sequence from beginWord to endWord. If no such sequence exists, return 0.

Example 1

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

Output: 5

One shortest sequence is "hit" -> "hot" -> "dot" -> "dog" -> "cog", which contains 5 words.

Example 2

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

Output: 0

endWord "cog" is not present in wordList, so no valid sequence can end at it.

Constraints

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord, endWord, and wordList[i] consist of lowercase English letters
beginWord != endWord
All the words in wordList are unique

Breadth-First Search over the Word Graph

Treat words as nodes joined when they differ by one letter, then BFS level by level, generating one-letter variants and enqueuing those present in the word set.

Loading animation…

Intuition

Think of each word as a node, with an edge connecting two words that differ in exactly one letter. The shortest transformation sequence is then the shortest path in this graph, which breadth-first search computes level by level. Instead of comparing every pair of words, we generate each one-letter variant of the current word and check membership in a hash set built from the word list, which is far faster. Every time we reach a new word we remove it from the set, ensuring each word is processed only once. The level count, starting at 1 for beginWord, equals the number of words on the path when we first meet endWord.

Algorithm walkthrough

1Put the word list into a hash set for O(1) lookups; if endWord is absent, return 0 because the target is unreachable.
2Seed a queue with beginWord and set the current level to 1, where the level counts the words in the sequence so far.
3Process the queue one full level at a time; if any dequeued word equals endWord, return the current level.
4For each word, replace each position with every letter from a to z to form candidate words.
5Whenever a candidate exists in the set, remove it and enqueue it for the next level so it is never revisited.
6After a level finishes, increment the level; if the queue drains without reaching endWord, return 0.

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])
        level = 1
        while queue:
            for _ in range(len(queue)):
                word = queue.popleft()
                if word == endWord:
                    return level
                for i in range(len(word)):
                    for c in "abcdefghijklmnopqrstuvwxyz":
                        candidate = word[:i] + c + word[i + 1:]
                        if candidate in word_set:
                            word_set.remove(candidate)
                            queue.append(candidate)
            level += 1
        return 0

Time

O(N * L^2)

Space

O(N * L)

N is the number of words and L the word length. For each word we try L positions times 26 letters and build a length-L candidate. The hash set holds up to N words of length L.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Dial Code Rewrite is our own problem on the technique behind Word Ladder: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free