Word Ladder II

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].

For example:

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"

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.

from collections import defaultdict, deque


def findLadders(beginWord: str, endWord: str, wordList: list[str]) -> list[list[str]]:
    # Convert wordList to a set for faster lookup
    wordList = set(wordList)

    # If the endWord is not in the wordList, there is no solution
    if endWord not in wordList:
        return []

    # Build adjacency list (graph)
    adj = defaultdict(list)
    all_words = wordList | {beginWord}
    for word1 in all_words:
        for word2 in all_words:
            if word1 != word2 and differ_by_one_letter(word1, word2):
                adj[word1].append(word2)

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

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

        if len(path) > shortest_len:
            break  # Optimization: paths longer than shortest are useless

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

        for neighbor in adj[word]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    # Filter out paths that are longer than the shortest path
    final_result = []
    for path in result:
        if len(path) == shortest_len:
            final_result.append(path)

    return final_result


def differ_by_one_letter(word1: str, word2: str) -> bool:
    diff_count = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            diff_count += 1

    return diff_count == 1


# Example Usage
beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
print(findLadders(beginWord, endWord, wordList))

beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log"]
print(findLadders(beginWord, endWord, wordList))

Explanation:

1. findLadders(beginWord, endWord, wordList) function:

   • Takes beginWord, endWord, and wordList as input.
   • Converts wordList to a set for efficient lookup.
   • Handles the case where endWord is not in wordList by returning an empty list.
   • Builds an adjacency list (graph) where nodes are words, and edges connect words that differ by one letter.
   • Performs Breadth-First Search (BFS) to find all shortest paths from beginWord to endWord.
     • Uses a queue to store paths to explore.
     • Maintains a visited set to avoid cycles.
     • Optimizes by breaking early if the current path's length exceeds the shortest length found so far.
   • Filters the results to include only the shortest paths.
   • Returns a list of shortest paths.

2. differ_by_one_letter(word1, word2) function:

   • Helper function to determine if two words differ by exactly one letter.
   • Returns True if they differ by one letter, False otherwise.

Big O Analysis:

• Time Complexity: O(V + E), where V is the number of vertices (words) and E is the number of edges in the graph.
  • Building the adjacency list takes O(N^2 * L) time, where N is the number of words and L is the length of the words. This is because we iterate through all pairs of words and compare them. However, this can be considered V^2 * L where V is the number of words we consider nodes.
  • BFS takes O(V + E) time to explore the graph. In the worst case, we might visit all vertices and edges.
  • Filtering the result takes O(K * S) time, where K is the number of shortest paths and S is the length of the shortest path.
• Space Complexity: O(V + E) to store the adjacency list, and O(W) for the queue and visited set during BFS, where W is the number of words. The space complexity of the result list could be O(K * S) in the worst case.

Edge Cases:

1. endWord not in wordList:

   • The code handles this case by returning an empty list if endWord is not present in wordList.

2. No transformation sequence exists:

   • If there is no path from beginWord to endWord, the BFS will terminate without finding any paths, and an empty list will be returned.

3. beginWord and endWord are the same:

   • The problem statement says beginWord != endWord so we can skip this check.

4. Empty wordList:

   • If the wordList is empty and the beginWord and endWord are different, it will return an empty list.

5. Large wordList:

   • The code might become slow for very large wordList due to the time complexity of building the adjacency list (O(N^2 * L)). Optimizations like pre-computing neighbors for each word can be employed, if required, in a production environment.