Word Ladder — C++ Coding Problem
Difficulty: hard | Category: graph
Problem Description
A **transformation sequence** from word `beginWord` to word `endWord` using a dictionary `wordList` is a sequence `beginWord → s₁ → s₂ → ... → sₖ → endWord` such that: - Every adjacent pair of words differs by exactly one letter. - Every word in the sequence is in `wordList`. Given `beginWord`, `endWord`, and `wordList`, return the **number of words** in the shortest transformation sequence, or `0` if no such sequence exists. **Approach:** BFS — at each step, try all single-character mutations.
Examples
Example 1
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: "hit" → "hot" → "dot" → "dog" → "cog" (5 words).
Example 2
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0