Word Ladder II

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s<sub>1</sub> -> s<sub>2</sub> -> ... -> s<sub>k</sub> such that:

• Every adjacent pair of words differs by a single letter.
• Every s<sub>i</sub> for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
• s<sub>k</sub> == 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, s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>k</sub>].

For example:

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 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Constraints:

• 1 <= beginWord.length <= 5
• endWord.length == beginWord.length
• 1 <= wordList.length <= 500
• wordList[i].length == beginWord.length
• beginWord, endWord, and wordList[i] consist of lowercase English letters.
• beginWord != endWord
• All the words in wordList are unique.
• The sum of all shortest transformation sequences does not exceed 10<sup>5</sup>.

from collections import deque

def find_ladders(beginWord: str, endWord: str, wordList: list[str]) -> list[list[str]]:
    """
    Finds all the shortest transformation sequences from beginWord to endWord using a dictionary wordList.

    Args:
        beginWord: The starting word.
        endWord: The target word.
        wordList: A list of words to use in the transformation.

    Returns:
        A list of lists, where each inner list is a shortest transformation sequence.
        Returns an empty list if no such sequence exists.
    """

    word_set = set(wordList)
    if endWord not in word_set:
        return []

    # BFS to find shortest paths
    queue = deque([(beginWord, [beginWord])])
    visited = {beginWord}
    shortest_length = float('inf')
    result = []

    while queue:
        word, path = queue.popleft()

        if len(path) > shortest_length:
            break

        if word == endWord:
            shortest_length = len(path)
            result.append(path)
            continue

        for i in range(len(word)):
            for char_code in range(ord('a'), ord('z') + 1):
                new_word = word[:i] + chr(char_code) + word[i + 1:]

                if new_word in word_set:
                    if new_word not in visited:
                        visited.add(new_word)
                        queue.append((new_word, path + [new_word]))

                    # Optimization: If the new word is already in the current path, do not revisit. Avoids cycles.
                    elif new_word in path:
                        continue

    # Filter out paths that are not of the shortest length
    shortest_paths = [path for path in result if len(path) == shortest_length]
    return shortest_paths


# Example Usage:
beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
result = find_ladders(beginWord, endWord, wordList)
print(f"Shortest transformation sequences: {result}")  # Output: [['hit', 'hot', 'dot', 'dog', 'cog'], ['hit', 'hot', 'lot', 'log', 'cog']]

beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log"]
result = find_ladders(beginWord, endWord, wordList)
print(f"Shortest transformation sequences: {result}")  # Output: []

Naive Approach (Brute Force):

1. Generate all possible sequences of words starting from beginWord.
2. Check if each sequence transforms to endWord and only contains words from wordList.
3. Find the shortest among all valid sequences.

This approach would be extremely inefficient because it explores all possible paths, leading to a combinatorial explosion. Its time complexity is exponential.

Optimal Approach (BFS):

The optimal approach uses Breadth-First Search (BFS) to find the shortest paths. BFS guarantees that the first time we reach endWord, we've found the shortest path to it.

1. Initialization:
   • Create a queue to store the words to visit, starting with beginWord.
   • Use a set to keep track of visited words to avoid cycles.
2. BFS Traversal:
   • While the queue is not empty:
     • Dequeue a word and its corresponding path.
     • For each possible one-letter transformation of the current word:
       • If the transformed word is in wordList and not visited:
         • Enqueue the transformed word and its path.
         • Mark the transformed word as visited.
       • If the transformed word is the endWord:
         • Add the path to the result.
3. Result:
   • Return the shortest paths found.

Big(O) Time Complexity Analysis:

• Let N be the number of words in wordList and L be the length of each word.
• BFS Traversal: In the worst case, we might visit all words in wordList. For each word, we generate all possible one-letter transformations. There are L positions in each word, and each position can have 26 possible characters. So, we generate 26 * L new words for each word visited.
• Overall: The time complexity is approximately O(N * 26 * L), which simplifies to O(N * L) since 26 is a constant. However, because we are looking for all shortest paths, in the worst case, we might have multiple shortest paths to explore, which could potentially increase the complexity, but it's still largely bound by O(N*L) for the core BFS process.

Big(O) Space Complexity Analysis:

• Queue: In the worst case, the queue might contain all the words in wordList, so O(N).
• Visited Set: We store visited words in a set, so O(N).
• Paths: In the worst-case scenario (very unusual, but possible), we might have to store many shortest paths. The problem states that the sum of all shortest transformation sequences does not exceed 10^5. Let's denote this as K. So, space for paths is O(K).
• Overall: The space complexity is O(N + K). Since K can be larger than N in some cases where many shortest paths exist, the dominant factor is O(K).

Edge Cases and How to Handle Them:

1. endWord Not in wordList:
   • Return an empty list immediately.
2. beginWord == endWord:
   • Return an empty list since the problem states beginWord != endWord.
3. No Transformation Sequence Exists:
   • BFS will terminate, and an empty list will be returned if endWord is never reached.
4. Empty wordList:
   • If endWord isn't beginWord, return an empty list.
5. Cycles:
   • Use a visited set to prevent revisiting words, avoiding infinite loops. Also make sure the word is not already in the current path.