Word Ladder

## Problem A **transformation sequence** from word `beginWord` to word `endWord` using a dictionary `wordList` is a sequence of words `beginWord -> s1 -> s2 -> ... -> sk` such that: - Every adjacent pair of words differs by a single letter. - Every `si` for `1 <= i <= k` is in `wordList`. Note that `beginWord` does not need to be in `wordList`. - `sk == endWord` Given two words `beginWord` and `endWord`, and a dictionary `wordList`, return the **number of words in the shortest transformation sequence** from `beginWord` to `endWord`, or `0` if no such sequence exists. ## 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 in the sequence) ``` **Example 2:** ``` Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: 0 Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence. ``` **Example 3:** ``` Input: beginWord = "a", endWord = "c", wordList = ["a","b","c"] Output: 2 Explanation: a -> c (single letter change, 2 words in sequence) ``` ## Approach Hints Use BFS. Start from `beginWord` and explore all one-letter transformations. Use a set for `wordList` to check membership in O(1). Track visited words to avoid cycles. The BFS level when `endWord` is found is the answer (add 1 for `beginWord`).