Return the number of words in the shortest transformation sequence from beginWord to endWord, changing one letter at a time, where every intermediate word is in the word list. Return 0 if none exists.
Before you code
Each word is a vertex; two words are neighbors if they differ in exactly one position. The graph is never built in full: generate a word's neighbors when you dequeue it.
Hints
- Put the word list in a set for O(1) membership.
- For each position and each letter a–z, form the candidate and check the set. Remove words from the set when you enqueue them, which doubles as the visited set.
- Faster neighbor lookup: group words by patterns such as
h*t. - Bidirectional BFS from both ends can cut the work dramatically.
Production & complexity notes
When solving Word ladder on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Breadth-first search to reinforce the underlying pattern.
What it practices
BFS shortest paths on a graph defined by a rule, from Breadth-first search.