Word Ladder

Q: Can bidirectional BFS make Word Ladder faster?

Yes. Search from beginWord and from endWord at once, always growing the smaller side by one level, and stop when a new word is already reached by the other side. The ladder then has one word more than the changes made on both sides together. If each word has about b neighbours and the ladder takes d changes, one search can touch about b^d words, while two searches that meet in the middle touch about 2 × b^(d/2) .

HardGraphs Queue

+10

You get two words, beginWord and endWord, and a list of words wordList. A ladder is a sequence of words that starts with beginWord, ends with endWord, and changes exactly one letter from each word to the next. Every word after beginWord must come from wordList.

Return the number of words in the shortest ladder, counting both ends, or 0 if no ladder exists. For example, cold, cord, card is a ladder of 3 words. beginWord does not have to be in wordList, but endWord does.

Function

ladderLength(beginWord: string, endWord: string, wordList: string-array) → integer

beginWordstring: the first word of the ladder
endWordstring: the word the ladder must reach
wordListstring-array: the words every later step must come from
Returnsinteger: the number of words in the shortest ladder, or 0 if there is none

Constraints

1 ≤ beginWord.length ≤ 10
endWord and every word in wordList have the same length as beginWord.
1 ≤ wordList.length ≤ 5000
All words hold only lowercase English letters.
beginWord != endWord
The words in wordList are all different. beginWord may or may not be one of them.

Examples

Input: beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
Output: 4
Explanation: lead and gold differ in three letters, so no ladder has fewer than 4 words, and lead, load, goad, gold has exactly 4. lend and lewd are one letter from lead too, but neither leads anywhere new, and bold can only be reached from gold itself.

Input: beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
Output: 0
Explanation: cat, cot, cog gets within one letter of dog, but dog is not in the list, so no ladder can end there.

Input: beginWord = "ab"endWord = "cd"wordList = ["ab", "cb", "cd", "ad"]
Output: 3
Explanation: ab, ad, cd and ab, cb, cd both take 3 words. ab is also in the list, but the start is counted once either way.

+14 hidden tests on Submit

Follow-up

Can you return one shortest ladder itself, the words in order, and not only its length?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Treat the words as the nodes of a graph, with an edge between two words that differ in one letter. A ladder is then a path from beginWord to endWord, and every edge costs the same, so the shortest ladder is the path with the fewest edges. Breadth-first search finds exactly that. What makes the problem hard is finding the edges fast: comparing every pair of 5,000 words is 25 million comparisons, so the best solution looks neighbours up through wildcard patterns instead. Below, n is the number of words and L their length.

Try every ladder with depth-first search

Correct, but does not finish on the largest tests

Intuition

Start at beginWord. From the current word, try every unused word that is one letter away and go deeper from it. When you reach endWord, record the ladder's length if it is the shortest so far. Mark the words on the current path as used so a ladder never loops back on itself, and free each word when you back out of it so other ladders can use it. Once you have a ladder of best words, stop extending any path that already has best-1 words: it cannot finish shorter.

This is correct because it tries every ladder that never repeats a word, and a shortest ladder never repeats one: if a word appeared twice, cutting out the part between the two copies would give a shorter ladder.

It is slow because the number of ladders explodes. Take 26 words that differ only in their first letter, aaa, baa up to zaa: every pair is one letter apart, so the search can wander through them in any order before it moves on, and 26 words can be ordered in about 4 × 10^26 ways. The cut only helps once some ladder is found. When endWord cannot be reached at all, nothing is ever cut, and a list of 34 words is already more than the search can finish. The recursion also goes as deep as the ladder, which can be thousands of words.

Algorithm

Mark beginWord as used if it is in the list, and set best to 0.
Write search(word, length). If word is endWord, keep length when it beats best, and return.
If best is not 0 and length + 1 ≥ best, return: this path cannot win.
For every unused word one letter away from word, mark it used, call search(next, length + 1), then unmark it.
Call search(beginWord, 1) and return best, which stays 0 if no ladder exists.

def ladderLength(beginWord, endWord, wordList):
    def one_letter_apart(a, b):
        differences = 0
        for x, y in zip(a, b):
            if x != y:
                differences += 1
                if differences > 1:
                    return False
        return differences == 1

    best = 0  # words in the shortest sequence found so far, 0 while there is none
    used = [word == beginWord for word in wordList]  # words on the current path

    def search(word, length):
        nonlocal best
        if word == endWord:
            if best == 0 or length < best:
                best = length
            return
        if best != 0 and length + 1 >= best:
            return  # any longer path cannot beat the best one
        for i, candidate in enumerate(wordList):
            if not used[i] and one_letter_apart(word, candidate):
                used[i] = True
                search(candidate, length + 1)
                used[i] = False  # free the word for other paths

    search(beginWord, 1)
    return best

Breadth-first search, comparing every pair

Correct, but does not finish on the largest tests

Intuition

Breadth-first search explores the words in order of distance. First beginWord, a ladder of 1 word. Then every word one letter away from it, ladders of 2. Then every new word one letter away from those, ladders of 3, and so on. A queue keeps that order: words leave it in the order they joined, so all words at distance d leave before any word at distance d + 1.

That order is why the first ladder BFS finds is a shortest one. When a word is first reached at distance d, every word closer than d has already been explored, so if a shorter ladder to it existed, the search would have reached the word earlier. The same argument makes it safe to mark a word visited the moment it joins the queue: its distance is final, and reaching it again later can only be longer. So each word joins the queue once, and as soon as endWord turns up as a neighbour, its distance is the answer.

This version finds the neighbours of a word by comparing it with every word in the list, letter by letter, and stopping at the second difference. Each of up to n words leaving the queue costs n comparisons of up to L letters, so O(n² × L) in total. With 5,000 words and a search that visits most of them, that is up to 25 million word comparisons. A compiled language gets through that quickly, but Python needs several seconds on the largest test.

Algorithm

If endWord is not in wordList, return 0.
Put beginWord in a queue with length 1. Mark it visited if it is in the list.
Take the next word and its length from the queue.
Compare it with every unvisited word in the list. For each one exactly one letter away: if it is endWord, return length + 1; otherwise mark it visited and add it with length + 1.
If the queue runs empty, endWord is unreachable: return 0.

from collections import deque


def ladderLength(beginWord, endWord, wordList):
    def one_letter_apart(a, b):
        differences = 0
        for x, y in zip(a, b):
            if x != y:
                differences += 1
                if differences > 1:
                    return False
        return differences == 1

    if endWord not in wordList:
        return 0
    visited = [word == beginWord for word in wordList]
    queue = deque([(beginWord, 1)])  # (word, words in the sequence up to it)
    while queue:
        word, length = queue.popleft()
        # Compare against every word to find the neighbours.
        for i, candidate in enumerate(wordList):
            if not visited[i] and one_letter_apart(word, candidate):
                if candidate == endWord:
                    return length + 1
                visited[i] = True
                queue.append((candidate, length + 1))
    return 0

Breadth-first search with wildcard buckets

Intuition

Keep the breadth-first search and make finding neighbours cheap. Two words are one letter apart exactly when hiding the same position in both makes them equal: hot and hit both become h*t. So give every word L patterns, one per hidden position, and add the word to a bucket for each pattern. The neighbours of a word are the other words in its L buckets, found by L hash lookups instead of a pass over the whole list.

Here is the search on the first example. lead has the patterns *ead, l*ad, le*d and lea*. The bucket l*ad holds load and le*d holds lend and lewd, so level 2 is those three words. From load, the bucket *oad gives goad at level 3, and from goad, go*d gives gold at level 4.

One more saving: when a word's bucket has been scanned, every word in it has been reached, so empty it. Later words that share the pattern would find nothing new there anyway. In the test where aaa, baa up to zaa share *aa, that bucket of 26 words is scanned once instead of 26 times. So the search reads each of the n × L bucket entries at most once.

Building the patterns takes n × L strings of L letters, O(n × L²) time and space, and the search costs the same: each word leaving the queue builds its L patterns again. For 5,000 words of 10 letters that is about 500,000 letter steps, against up to 250 million for the pairwise comparison.

Algorithm

If endWord is not in wordList, return 0.
For every word in the list, and for beginWord, add the word to the bucket of each of its L patterns.
Start the queue with beginWord, mark it visited, and set the length to 1.
Process the queue one level at a time. If a word is endWord, return the length. Otherwise, for each of its patterns, add every unvisited word in that bucket to the next level, mark it visited, and empty the bucket.
After each level, add 1 to the length. If the queue runs empty, return 0.

from collections import defaultdict, deque


def ladderLength(beginWord, endWord, wordList):
    if endWord not in wordList:
        return 0
    size = len(beginWord)
    # "h*t" -> every word that matches it: hot, hat, hit... are one letter apart.
    buckets = defaultdict(list)
    for word in set(wordList) | {beginWord}:
        for i in range(size):
            buckets[word[:i] + "*" + word[i + 1:]].append(word)
    visited = {beginWord}
    queue = deque([beginWord])
    length = 1  # words in the sequence up to the current level
    while queue:
        for _ in range(len(queue)):  # one level: every word at this distance
            word = queue.popleft()
            if word == endWord:
                return length
            for i in range(size):
                pattern = word[:i] + "*" + word[i + 1:]
                for neighbour in buckets[pattern]:
                    if neighbour not in visited:
                        visited.add(neighbour)
                        queue.append(neighbour)
                buckets[pattern] = []  # all of them are visited now: never scan it again
        length += 1
    return 0

Pitfalls and edge cases

Most wrong answers come from counting the wrong thing or from the rule about endWord.

Returning the number of changes instead of the number of words. lead to gold takes 3 changes and 4 words, and the answer is 4.
Not checking that endWord is in wordList. In the second example, the search gets one letter from dog, but the answer is 0.
Using depth-first search and returning the first ladder it finds. DFS follows one branch as far as it goes, so its first ladder is often long.
Marking a word visited when it leaves the queue instead of when it joins. A word in a full bucket of 26 can then join the queue up to 25 times, and the queue grows far past n.
Leaving beginWord unmarked when it is also in wordList. The search then reaches it again two levels later and repeats work. Mark it visited from the start.
Testing for words that differ in at most one letter. Every word differs from itself in zero letters, so the condition is exactly one.
Recursing along the ladder. A hidden test has a shortest ladder of 1,500 words, deep enough to overflow the call stack in some languages. BFS needs only a queue.

Frequently asked questions4

Why does breadth-first search find the shortest word ladder?

BFS explores the words in rounds: first the start, then every word one change away, then every word two changes away. A word is reached for the first time in the earliest round that can reach it, so its distance is the fewest changes possible. That only works because every change counts the same. With different costs per step you would need Dijkstra's algorithm instead.

What is the time complexity of Word Ladder?

With wildcard buckets, building the patterns and running the search take O(n × L²) time for n words of length L, since each word has L patterns of L letters. Comparing every pair of words instead costs O(n² × L), and trying every ladder with depth-first search is exponential.

How do you find the words that are one letter away?

One way is the wildcard buckets above: words that share a pattern such as h*t are neighbours. The other is to change each position of the word to each of the 26 letters and look the result up in a hash set of the words. That costs 26 × L lookups per word, each hashing L letters, so O(n × 26 × L²) in total. Both beat comparing against the whole list.

Can bidirectional BFS make Word Ladder faster?

Yes. Search from beginWord and from endWord at once, always growing the smaller side by one level, and stop when a new word is already reached by the other side. The ladder then has one word more than the changes made on both sides together. If each word has about b neighbours and the ladder takes d changes, one search can touch about b^d words, while two searches that meet in the middle touch about 2 × b^(d/2).

Python

def ladderLength(beginWord, endWord, wordList):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

beginWord = "lead"
endWord = "gold"
wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]

Expected

Word Ladder

Function

Constraints

Examples

Hints

Solution

Try every ladder with depth-first search

Breadth-first search, comparing every pair

Breadth-first search with wildcard buckets

Pitfalls and edge cases

Frequently asked questions4

Similar problems