Word ladder

The direct baseline compares every pair of dictionary words and stores an edge when exactly one character differs. For N words of length L this costs O(N²L), even if the reachable component is tiny. DFS can find a route but its first route need not be shortest: exploration order can follow a long detour first.

Instead generate each one-character replacement on demand. Check membership in a set, mark the word discovered immediately, and save its parent. The BFS queue contains the current distance layer followed by the next. Invariant: the first discovery of a word fixes its minimum move count, because every generating parent has the smallest unprocessed distance. Marking only on removal permits duplicate queue entries and redundant parent assignment.

The fixed 26-letter alphabet does not make Python string creation free. Each of 26L candidates costs O(L) to construct/hash, giving O(NL²) search time in the worst case, plus O(NL) input validation. Stored dictionary and discovered strings use O(NL) space; parent/queue entries add O(N). The returned path uses O(PL) if its strings are counted, with P words. No quadratic adjacency table is retained.

Follow-up 1 — return every shortest path. Predict what is lost when cog stores only dog. Save all parents at the preceding depth, finish the entire winning layer, and traverse the resulting parent DAG. Output may be exponential; report output-sensitive bounds rather than promising linear total work.

Follow-up 2 — large dictionary, one pair. Bidirectional BFS expands the smaller frontier from start/end and joins compatible layers. Keep separate visited/depth maps and reconstruct both halves. It can reduce explored states but does not remove the need to account for neighbor generation or prove the stopping rule.

Senior depth is deriving the implicit graph and proving shortestness. Lead depth adds dictionary versioning and query-memory limits if this becomes a service.

Reference: solution.py (download file, source below); tests validate actual edges, optimal length, unreachable endpoints, identity, duplicates, and malformed words.

"""Shortest one-character transformation using an implicit unweighted graph."""
from collections import deque
from string import ascii_lowercase


def word_ladder(start, end, words):
    """Return endpoint-inclusive shortest path, or []; words are lowercase ASCII."""
    words = set(words)
    if not start or len(start) != len(end):
        raise ValueError("endpoints must have equal positive length")
    if any(len(w) != len(start) or any(c not in ascii_lowercase for c in w)
           for w in words | {start, end}):
        raise ValueError("words must have equal length and lowercase ASCII letters")
    if start == end:
        return [start]
    if end not in words:
        return []
    parent = {start: None}
    queue = deque([start])
    while queue:
        word = queue.popleft()
        for i in range(len(word)):
            for char in ascii_lowercase:
                if char == word[i]:
                    continue
                candidate = word[:i] + char + word[i + 1:]
                if candidate in words and candidate not in parent:
                    parent[candidate] = word
                    if candidate == end:
                        path = [end]
                        while parent[path[-1]] is not None:
                            path.append(parent[path[-1]])
                        return path[::-1]
                    queue.append(candidate)
    return []

python -m unittest discover -s curriculum/01-code/02-data-structures-algorithms/problems/22-word-ladder -p 'test_*.py'