leetcode-126 Word Ladder II

# Return all shortest transformation sequences from beginWord to endWord.

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        from collections import defaultdict, deque

        if endWord not in wordList:
            return []

        word_set = set(wordList)
        # BFS to build graph and find distances
        graph = defaultdict(list)
        distance = {beginWord: 0}
        queue = deque([beginWord])

        while queue:
            word = queue.popleft()
            if word == endWord:
                break

            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    next_word = word[:i] + c + word[i+1:]
                    if next_word in word_set:
                        if next_word not in distance:
                            distance[next_word] = distance[word] + 1
                            queue.append(next_word)

                        if distance[next_word] == distance[word] + 1:
                            graph[word].append(next_word)

        # Backtrack to find all paths
        result = []
        def backtrack(path):
            if path[-1] == endWord:
                result.append(path[:])
                return

            for next_word in graph[path[-1]]:
                path.append(next_word)
                backtrack(path)
                path.pop()

        backtrack([beginWord])
        return result

# Time: O(N * 26^L), Space: O(N)
# AirBnB: Advanced BFS + backtracking combination