Word Ladder II: Finding All Shortest Transformation Paths

This problem asks you to find all shortest transformation sequences from a given beginWord to a endWord using a provided dictionary of words. A transformation sequence is valid if each adjacent pair of words differs by exactly one letter, and each word in the sequence (except the beginWord) exists in the dictionary. This is a classic graph traversal problem with an emphasis on finding all shortest paths.

Problem Description

Given a beginWord, an endWord, and a wordList, you need to return all possible shortest transformation sequences from beginWord to endWord.

A transformation sequence is defined as follows:

1. The first word is beginWord.
2. The last word is endWord.
3. For any two consecutive words word1 and word2 in the sequence, they must differ by exactly one letter.
4. Every intermediate word word in the sequence must exist in the wordList. Note that beginWord does not need to be in wordList. endWord must be in wordList to be reachable.

If there are multiple shortest transformation sequences, return all of them. If no such sequence exists, return an empty list.

Key Requirements:

• Find all shortest transformation sequences.
• Each word transformation must differ by exactly one letter.
• All intermediate words must be in the provided wordList.

Important Considerations:

• The wordList can contain duplicates. However, for the purpose of finding paths, each unique word in wordList should be treated as a distinct node in our potential graph.
• The beginWord and endWord are case-sensitive and will consist of lowercase English letters.
• All words in wordList will have the same length as beginWord and endWord.

Examples

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: There are two shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"
Both sequences are of length 5 and differ by one letter at each step.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in the wordList. Therefore, no transformation sequence can reach it.

Example 3:

Input: beginWord = "a", endWord = "c", wordList = ["a","b","c"]
Output: [["a","c"]]
Explanation: The word "b" is not needed to form a shortest path.

Constraints

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord, endWord, and wordList[i] consist of lowercase English letters.
• beginWord != endWord
• endWord will be present in wordList. (This constraint is relaxed from the problem description to allow for cases where endWord might not be present, as shown in Example 2. The actual problem might have endWord guaranteed to be in wordList. If endWord is not in wordList, an empty list should be returned.)
• All words in wordList are unique. (This constraint is typically present in such problems, but if not, the logic should handle duplicates appropriately by effectively treating them as the same node.)
• The number of words in wordList is up to 5000.
• The length of each word is up to 10.
• The solution should aim for reasonable performance, avoiding brute-force exponential time complexity.

Notes

• This problem can be modeled as finding shortest paths in an unweighted graph. The words are nodes, and an edge exists between two words if they differ by exactly one character.
• Since we need to find all shortest paths, a standard Breadth-First Search (BFS) is a good starting point. BFS naturally finds the shortest path length. However, to reconstruct all shortest paths, you'll need to augment the BFS.
• Consider how to efficiently determine which words are "neighbors" (differ by one letter). Preprocessing or a helper function can be useful here.
• Think about how to keep track of paths during the BFS. A common approach involves storing parent pointers or building paths as you explore.
• Be mindful of cycles and avoiding redundant explorations.
• Consider the time complexity. A naive approach of checking all permutations or all possible word transformations for each step will be too slow.