Word Ladder

hardTests passed 2026-11-11v1.0.0
TC: O(N * L^2)|SC: O(N * L)
GraphsOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Avoid O(N^2 * L) pairwise comparisons by indexing dictionary words onto wildcard patterns (`h*t -> ["hot", "hit"]`), or run **bidirectional BFS** generating 26 char substitutions per position on the smaller frontier.

2. Complexity Bounds & Proof

Wait: with wordSet lookup over L indices × 26 chars, generating next words runs in O(L^2 * 26) per word instead of scanning N words.

3. Minimal Idiomatic Code

def ladderLength(beginWord: str, endWord: str, wordList: list[str]) -> int:
    words = set(wordList)
    if endWord not in words:
        return 0
    front, back = {beginWord}, {endWord}
    words.discard(beginWord)
    steps = 1
    while front and back:
        if len(front) > len(back):
            front, back = back, front
        nxt = set()
        for w in front:
            for i in range(len(w)):
                for ch in 'abcdefghijklmnopqrstuvwxyz':
                    cand = w[:i] + ch + w[i + 1:]
                    if cand in back:
                        return steps + 1
                    if cand in words:
                        words.remove(cand)
                        nxt.add(cand)
        front = nxt
        steps += 1
    return 0

4. Failure Modes & Interview Follow-ups

Pitfalls:- Returning edge distance instead of word count (`beginWord` counts as step `1`). - Checking `endWord not in wordSet` early avoids redundant graph expansion.
Follow-ups:- Word Ladder II stores parent DAGs per BFS level and backtracks all shortest paths.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Rotting Oranges (O(M * N))Word Break (O(N * W * L))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.