Word Ladder

Given beginWord, endWord, and a word list, return the length of the shortest transformation sequence from beginWord to endWord such that:

• You may change exactly one letter at a time.
• Each intermediate word must exist in the word list.

Return 0 if no such sequence exists.

Function signature

func LadderLength(beginWord, endWord string, wordList []string) int

Inputs / outputs

• beginWord, endWord: lowercase words of the same length.
• wordList: list of allowed intermediate words.
• Return: length of the shortest sequence, or 0.

Example

begin = "hit", end = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5 (hit -> hot -> dot -> dog -> cog)

Constraints

• 1 <= len(wordList) <= 50_000
• word length <= 10

Core idea (near-solution)

Use BFS on words. To generate neighbors efficiently, precompute wildcard patterns (replace one letter with *). All words sharing a pattern are one step apart.

Invariant: BFS explores words in increasing transformation distance.

Algorithm (step-by-step)

1. Put all words into a set; if endWord not present, return 0.
2. Build a map from wildcard pattern to words (e.g., h*t -> hot, hat).
3. BFS from beginWord. For each word, generate its patterns and enqueue unseen neighbors.
4. The first time you reach endWord, return the distance.

Correctness sketch

• Invariant: BFS explores words in increasing transformation distance.
• BFS explores nodes in increasing distance from the sources.
• The first time a node is visited is its shortest distance.
• Therefore the recorded distance/level is optimal.

Trace (hand walkthrough)

Example input:
begin = "hit", end = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5 (hit -> hot -> dot -> dog -> cog)

Walk:
- level 1: hit -> hot
- level 2: hot -> dot, lot
- level 3: dot->dog, lot->log
- level 4: dog/log -> cog -> length 5

Pitfalls to avoid

• Not marking visited on enqueue (causes repeated work).
• Forgetting to check if endWord is in the dictionary.

Complexity

• Time: O(N * L^2) with precomputed patterns (N words, L word length).
• Extra space: O(N * L) for pattern buckets.

Implementation notes (Go)

• Precompute wildcard pattern buckets for O(1) neighbor lookup.
• Mark words visited on enqueue to avoid duplicates.