Loading 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 all the **shortest transformation sequences** from `beginWord` to `endWord`, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words `[beginWord, s1, s2, ..., sk]`.
Example 1
Input: beginWord = hit, endWord = cog, wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation: Two shortest ladders of length 5 connect hit to cog.
Example 2
Input: beginWord = hit, endWord = cog, wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: endWord cog is not in the dictionary, so no sequence exists.
Example 3
Input: beginWord = a, endWord = c, wordList = ["a","b","c"]
Output: [["a","c"]]
Explanation: "a" becomes "c" in a single one-letter change, so the only shortest sequence is ["a","c"].
Do BFS one layer at a time, but instead of a single parent per word, remember every path that reaches a word at the current shortest distance. Expand the whole current layer simultaneously; stop the moment endWord appears so only shortest sequences are kept.
Run checks all cases above. Submit evaluates all test cases.