Hints — p25 Word Ladder

Read one at a time.

Hint 1 — Spot the graph. “Each step changes exactly one letter, intermediate word must be in dictionary, find SHORTEST sequence.” Words are nodes, edges connect words that differ by one letter, we want shortest distance. This is BFS on an implicit graph. Not DP, not DFS — BFS.

Hint 2 — Adjacency is the bottleneck. The graph isn’t given. Naive way: for every pair (a, b) of words, check if they differ by one letter → O(N²·L). For N=5000, L=10, that’s 2.5×10⁸ ops — borderline TLE in Python. You need faster adjacency.

Hint 3 — Bucket trick (the key insight). For each word, generate L patterns by replacing each letter with *. Example: "hit" → ["*it", "h*t", "hi*"]. Group all words by these patterns. Two words share a bucket iff they differ at exactly one position. Now adjacency lookup is O(L), not O(N·L).

Hint 4 — BFS bookkeeping.

• Mark visited when ENQUEUEING (not when dequeueing) to avoid duplicates.
• Track distance as (word, dist) tuples in the queue.
• Distance counts WORDS, including both endpoints — so beginWord starts at distance 1.
• Check endWord in wordList upfront; if absent, return 0 immediately.

Hint 5 — Bidirectional BFS (Hard follow-up). BFS from both ends simultaneously. Maintain two frontiers. At each step, EXPAND THE SMALLER ONE (this is crucial — without it you lose most of the speedup). When a neighbor lands in the other frontier, you’ve found the meeting point — return distance. Complexity drops from b^d to 2·b^(d/2). For huge dictionaries this is the difference between TLE and instant.

If still stuck: look at ladder_length_bucket_bfs in solution.py — the bucket adjacency + BFS combo is the whole problem. Bidirectional is a bonus optimization.