DSA Word Ladder

The problem

A word ladder changes one word into another through a chain of real words. Each step changes exactly one letter. Every word after the first must come from a given word list.

The answer is the number of words in the shortest ladder, counting both ends. The answer is 0 when no ladder exists. A target that is missing from the word list gives 0 at once.

base = ["hot", "dot", "dog", "lot", "log", "cog"]
cases = [
    ("hit", "cog", base, 5),
    ("hit", "log", base, 4),
    ("hit", "hot", base, 2),
    ("hit", "zzz", base, 0),
    ("hit", "mud", base + ["mud"], 0),
]
for begin, end, words, expected in cases:
    print(begin, "to", end, "over", len(words), "listed words ->", expected)

The last two cases fail for different reasons. The target zzz is not listed at all. The target mud is listed but sits alone, with no listed word one letter away from it.

Intuition: walk straight at the target

The first idea changes the first letter that differs from the target. Each change makes the current word look more like the target. The idea feels like progress, and it dies on the very first step.

A ladder is allowed to move sideways. The real first step from hit to hot changes a letter that the target cog does not even contain at that position in the same way. Resemblance to the target is the wrong compass.

words = {"hot", "dot", "dog", "lot", "log", "cog"}

def greedy_step(word, end):
    for i in range(len(word)):
        if word[i] != end[i]:
            return word[:i] + end[i] + word[i + 1:]
    return word

for start in ["hit", "hot"]:
    cand = greedy_step(start, "cog")
    print("greedy from", start, "tries", cand, "- in word list:", cand in words)

Both greedy tries land outside the word list, so both walks stop before they start. The shortest ladder exists, and its first step increases nothing measurable. A search that explores by distance in steps, not by resemblance, is needed.

Brute force: enumerate every ladder, keep the shortest

The brute force walks depth-first and writes down every complete ladder. A word never repeats inside one ladder, which keeps each walk finite. The shortest written ladder is the answer.

The enumeration pays for ladders that share long openings. The openings are rewalked for every ending, and the path count grows as the word list branches. A counter records the search calls so the waste is visible.

words = {"hot", "dot", "dog", "lot", "log", "cog"}

def neighbours(word):
    out = []
    for i in range(len(word)):
        for ch in "abcdefghijklmnopqrstuvwxyz":
            cand = word[:i] + ch + word[i + 1:]
            if cand in words and cand != word:
                out.append(cand)
    return sorted(out)

paths = []
calls = [0]

def dfs(word, path, seen):
    calls[0] += 1
    if word == "cog":
        paths.append(list(path))
        return
    for nb in neighbours(word):
        if nb not in seen:
            seen.add(nb)
            path.append(nb)
            dfs(nb, path, seen)
            path.pop()
            seen.remove(nb)

dfs("hit", ["hit"], {"hit"})
for path in sorted(paths):
    print("ladder:", " -> ".join(path))
print("ladders found:", len(paths))
print("shortest length:", min(len(p) for p in paths))
print("search calls:", calls[0])

Eight complete ladders hide in a six-word list, and the search makes 24 calls to find them all. Six of the eight ladders are longer than the answer. Breadth-first search avoids writing any of them down.

The optimal solution: breadth-first search, one length at a time

The state is a queue of words at the current ladder length, plus a seen set. Breadth-first search finishes every ladder of one length before starting the next, so the first arrival at the target is the shortest ladder.

Neighbours are generated by trying every letter in every position and keeping the candidates that sit in the word set. A word enters the seen set when it joins the queue, not when it leaves. That timing stops the same word from being queued twice in one level.

from collections import deque


def ladder_length(begin, end, word_list):
    words = set(word_list)
    if end not in words:
        return 0, 0
    words.add(begin)

    def neighbours(word):
        out = []
        for i in range(len(word)):
            for ch in "abcdefghijklmnopqrstuvwxyz":
                cand = word[:i] + ch + word[i + 1:]
                if cand in words and cand != word:
                    out.append(cand)
        return sorted(out)

    seen = {begin}
    queue = deque([begin])
    length = 1
    visited = 0
    while queue:
        for _ in range(len(queue)):
            word = queue.popleft()
            visited += 1
            if word == end:
                return length, visited
            for nb in neighbours(word):
                if nb not in seen:
                    seen.add(nb)
                    queue.append(nb)
        length += 1
    return 0, visited

base = ["hot", "dot", "dog", "lot", "log", "cog"]
cases = [
    ("hit", "cog", base, 5),
    ("hit", "log", base, 4),
    ("hit", "hot", base, 2),
    ("hit", "zzz", base, 0),
    ("hit", "mud", base + ["mud"], 0),
]
for begin, end, words, expected in cases:
    length, visited = ladder_length(begin, end, words)
    print(begin, "to", end, "->", length, "| expected:", expected, "| match:", length == expected, "| words visited:", visited)

All five cases from the start of the article pass. The unreachable target mud costs a full search of the reachable words before answering 0. The missing target zzz costs nothing, because the opening membership test rejects it.

Walkthrough: the levels from hit to cog

The walk runs the search level by level. Each level holds the words first reached at that ladder length. The seen set after each level is the union of all levels so far.

from collections import deque

words = {"hot", "dot", "dog", "lot", "log", "cog"}

def neighbours(word):
    out = []
    for i in range(len(word)):
        for ch in "abcdefghijklmnopqrstuvwxyz":
            cand = word[:i] + ch + word[i + 1:]
            if cand in words and cand != word:
                out.append(cand)
    return sorted(out)

seen = {"hit"}
queue = deque(["hit"])
length = 1
while queue:
    level = []
    for _ in range(len(queue)):
        word = queue.popleft()
        level.append(word)
        for nb in neighbours(word):
            if nb not in seen:
                seen.add(nb)
                queue.append(nb)
    print("length", length, "- words", sorted(level), "- seen so far", len(seen))
    if "cog" in level:
        break
    length += 1
print("cog reached at length:", length)

The target appears in the fifth level and nowhere earlier. That is the whole guarantee in one picture. No shorter ladder can exist, because levels one to four were finished first and cog is absent from all of them.

Complexity

The search visits each listed word at most once, so the queue and the seen set hold at most one entry per word, plus the starting word. The space is proportional to the word count, written O(N).

Neighbour generation dominates the time. Each visited word tries 26 letters in each position, so a word of L letters costs 26 times L candidate tests. The candidate count, not the word count alone, is the honest measure.

from collections import deque

def counted(begin, end, word_list):
    words = set(word_list)
    if end not in words:
        return 0, 0, 0
    words.add(begin)
    seen = {begin}
    queue = deque([begin])
    length = 1
    visited = 0
    tests = 0
    while queue:
        for _ in range(len(queue)):
            word = queue.popleft()
            visited += 1
            if word == end:
                return length, visited, tests
            for i in range(len(word)):
                for ch in "abcdefghijklmnopqrstuvwxyz":
                    tests += 1
                    cand = word[:i] + ch + word[i + 1:]
                    if cand in words and cand != word and cand not in seen:
                        seen.add(cand)
                        queue.append(cand)
        length += 1
    return 0, visited, tests

base = ["hot", "dot", "dog", "lot", "log", "cog"]
for end in ["hot", "log", "cog"]:
    length, visited, tests = counted("hit", end, base)
    print("hit to", end, "- length", length, "- words visited", visited, "- candidate tests", tests)

Reaching cog costs 468 candidate tests to visit seven words. Most tests miss the word set and produce nothing. That constant factor is the price of generating neighbours without an index, and it is paid per visited word.

Edge cases and pitfalls

An empty word list answers 0 for any target. The opening membership test fails, and the search never starts. The same test handles every missing target, listed neighbours or not.

A listed word of the wrong length is invisible to the search. Candidates are built by swapping one letter, so their length never changes. Marking a word as seen only when it leaves the queue is the other classic pitfall, because two parents in one level would then queue the same child twice.

from collections import deque


def ladder_length(begin, end, word_list):
    words = set(word_list)
    if end not in words:
        return 0, 0
    words.add(begin)

    def neighbours(word):
        out = []
        for i in range(len(word)):
            for ch in "abcdefghijklmnopqrstuvwxyz":
                cand = word[:i] + ch + word[i + 1:]
                if cand in words and cand != word:
                    out.append(cand)
        return sorted(out)

    seen = {begin}
    queue = deque([begin])
    length = 1
    visited = 0
    while queue:
        for _ in range(len(queue)):
            word = queue.popleft()
            visited += 1
            if word == end:
                return length, visited
            for nb in neighbours(word):
                if nb not in seen:
                    seen.add(nb)
                    queue.append(nb)
        length += 1
    return 0, visited

base = ["hot", "dot", "dog", "lot", "log", "cog"]
print("empty word list:", ladder_length("hit", "cog", [])[0])
print("four-letter word listed too:", ladder_length("hit", "cog", base + ["dogs"])[0])
print("start word also listed:", ladder_length("hit", "cog", base + ["hit"])[0])
print("one-letter change only:", ladder_length("hit", "hot", base)[0])

None of the extra listings move the answer. The ladder length is a property of the reachable words, not of the list padding. The count stays at five words from hit to cog.