Word Ladder

Problem

You are given a start word beginWord, a target word endWord, and a dictionary wordList. All words have the same length and consist of lowercase letters. A transformation sequence is a chain of words starting at beginWord and ending at endWord where each consecutive pair differs in exactly one letter, and every word after the first must be in wordList. Return the length of the shortest transformation sequence (counting both endpoints), or 0 if none exists.

• Words are at most 12 characters long, and the dictionary has at most a few thousand words.
• beginWord != endWord; beginWord need not be in wordList; all words in wordList are distinct.

Examples

• beginWord = "cat", endWord = "dog", wordList = ["cot","cog","dog","dot"] → 4. One shortest chain: cat → cot → cog → dog (or cat → cot → dot → dog).
• Same start and end, but wordList = ["cot","cog","dot"] → 0. dog is not in the dictionary, so it can never be reached.
• beginWord = "x", endWord = "z", wordList = ["x","y","z"] → 2. x → z directly, since they differ in only one letter.

Hints

1. Treat each word as a node. When are two words adjacent? What kind of path are you being asked for?
2. Comparing every pair of words to find neighbors costs O(N²·L). Can you generate a word's neighbors from the word itself?
3. BFS over the implicit graph; generate neighbors by replacing each position with each letter and checking membership in a set (or by grouping words under wildcard patterns like h*t).