Word Ladder: shortest transformation via BFS — how do you build the wildcard graph?

Q: Word Ladder: shortest transformation via BFS — how do you build the wildcard graph?

**Target Audience:** Beginners preparing for coding interviews — you know Python dicts and strings, and ideally have read the basic Word Ladder BFS; everything else is explained from scratch. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every output shown was produced by actually running the code with `python3` (3.13); nothing is typed in by hand. ## 1. Why This Even Matters — A Story First Crossword solvers own a strange kind of dictionary: it is sorted by **pattern**. Stuck on "H _ T"? Look up `h?t` and the book lists HAT, HIT, HOT, HUT on one line. You do not compare HOT against all 100,000 words in the language to find its one-letter relatives — you look up the three lines `?ot`, `h?t` and `ho?`, and every word on those lines is exactly one letter away. That is the **wildcard graph** for Word Ladder. The ba

The problem

Question presented to candidate: "In Word Ladder you BFS from a begin word to an end word, changing one letter per step, using only dictionary words. Instead of trying all 26 letters at every position, build a wildcard graph: group the words by patterns like h*t, and use those groups to find neighbours. Show how you build it and how the BFS uses it, in Python."

What a strong answer should cover:

The pattern idea: each word of length L yields L patterns (hot → *ot, h*t, ho*); two words are one letter apart iff they share a pattern.
Building pattern → [words] buckets in O(N · L²) time and memory, including beginWord.
BFS that looks up a word's L buckets for neighbours, marks visited on enqueue, and clears each bucket after scanning it so the whole search reads at most N · L entries.
Comparison with pairwise comparison (O(N² · L)) and with the 26-letter method (O(N · 26 · L²)), and the memory cost of the buckets.
Python specifics: collections.defaultdict(list) for building, .get(p, []) for reading so lookups do not insert empty buckets, and slicing w[:i] + "*" + w[i+1:] to make patterns.

Clarifying questions expected:

Are all words the same length, and is the dictionary reused for many queries?

Code / implementation expected: Yes — a Python build_buckets(words) with defaultdict(list) and a BFS ladder(begin, end, word_list) that uses and clears the buckets.

bfs
graph
Amazon

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you know Python dicts and strings, and ideally have read the basic Word Ladder BFS; everything else is explained from scratch. Difficulty: Medium Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every output shown was produced by actually running the code with python3 (3.13); nothing is typed in by hand.

1. Why This Even Matters — A Story First

Crossword solvers own a strange kind of dictionary: it is sorted by pattern. Stuck on "H _ T"? Look up h?t and the book lists HAT, HIT, HOT, HUT on one line. You do not compare HOT against all 100,000 words in the language to find its one-letter relatives — you look up the three lines ?ot, h?t and ho?, and every wor

The solution is hidden so you can try first

15 min read · 10 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonBuilding the wildcard buckets for the LeetCode list, then BFS through them

Practice

PythonPairwise comparison vs wildcard buckets, and BFS with vs without clearing buckets