Word ladder: fewest one-letter changes between two words

Given a start word, an end word and a list of words, all the same length, find the fewest single-letter changes that turn the start word into the end word. Each step changes exactly one letter, and every word you pass through, including the end word, must be in the list. Return -1 if it cannot be done.

Interface

Unless you agree on a different interface with the interviewer, assume:

• ladder_steps(begin: str, end: str, words: list[str]) -> int — the number of changes; 0 when begin == end.

Example

ladder_steps("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])   ->  4
# hit -> hot -> dot -> dog -> cog

ladder_steps("hit", "cog", ["hot", "dot", "dog", "lot", "log"])          ->  -1
# "cog" is not in the list

Constraints

• 1 <= len(begin) == len(end) <= 20; up to 50,000 distinct words; lowercase letters only.
• begin need not be in the list.

Clarifying questions

• Count the changes, or the words in the sequence? (Changes: one fewer than the words.)
• Must begin be in the list?
• Is the alphabet only lowercase English letters?

What a strong answer covers

• Model words as nodes and single-letter changes as edges; breadth-first search finds the shortest path because every edge costs 1.
• Finding neighbours fast: try all 26 letters at each position against a set (O(L · 26) per word), or group words by wildcard patterns such as h*t, built once in O(N · L).
• Marking words visited when they are enqueued, not when dequeued, so a word is never queued twice.
• Bidirectional search from both ends, which shrinks the frontier a lot on large dictionaries.
• Complexity: O(N · L · 26) time with the letter-swap method, O(N · L) memory.

Follow-ups

• Return one shortest sequence, then every shortest sequence.
• Steps can also insert or delete a letter.
• The dictionary is too large to fit in memory.