1
# Runtime: 80 ms (Top 72.71%) | Memory: 14.5 MB (Top 54.17%)
2
class Solution:
3

4
    WILDCARD = "."
5

6
    def findLadders(
7
        self, beginWord: str, endWord: str, wordList: List[str]
8
    ) -> List[List[str]]:
9
        """
10
        Given a wordlist, we perform BFS traversal to generate a word tree where
11
        every node points to its parent node.
12

13
        Then we perform a DFS traversal on this tree starting at the endWord.
14
        """
15
        if endWord not in wordList:
16
            # end word is unreachable
17
            return []
18

19
        # first generate a word tree from the wordlist
20
        word_tree = self.getWordTree(beginWord, endWord, wordList)
21

22
        # then generate a word ladder from the word tree
23
        return self.getLadders(beginWord, endWord, word_tree)
24

25
    def getWordTree(
26
        self, beginWord: str, endWord: str, wordList: List[str]
27
    ) -> Dict[str, List[str]]:
28
        """
29
        BFS traversal from begin word until end word is encountered.
30

31
        This functions constructs a tree in reverse, starting at the endWord.
32
        """
33
        # Build an adjacency list using patterns as keys
34
        # For example: ".it" -> ("hit"), "h.t" -> ("hit"), "hi." -> ("hit")
35
        adjacency_list = defaultdict(list)
36
        for word in wordList:
37
            for i in range(len(word)):
38
                pattern = word[:i] + Solution.WILDCARD + word[i + 1 :]
39
                adjacency_list[pattern].append(word)
40

41
        # Holds the tree of words in reverse order
42
        # The key is an encountered word.
43
        # The value is a list of preceding words.
44
        # For example, we got to beginWord from no other nodes.
45
        # {a: [b,c]} means we got to "a" from "b" and "c"
46
        visited_tree = {beginWord: []}
47

48
        # start off the traversal without finding the word
49
        found = False
50

51
        q = deque([beginWord])
52
        while q and not found:
53
            n = len(q)
54

55
            # keep track of words visited at this level of BFS
56
            visited_this_level = {}
57

58
            for i in range(n):
59
                word = q.popleft()
60

61
                for i in range(len(word)):
62
                    # for each pattern of the current word
63
                    pattern = word[:i] + Solution.WILDCARD + word[i + 1 :]
64

65
                    for next_word in adjacency_list[pattern]:
66
                        if next_word == endWord:
67
                            # we don't return immediately because other
68
                            # sequences might reach the endWord in the same
69
                            # BFS level
70
                            found = True
71
                        if next_word not in visited_tree:
72
                            if next_word not in visited_this_level:
73
                                visited_this_level[next_word] = [word]
74
                                # queue up next word iff we haven't visited it yet
75
                                # or already are planning to visit it
76
                                q.append(next_word)
77
                            else:
78
                                visited_this_level[next_word].append(word)
79

80
            # add all seen words at this level to the global visited tree
81
            visited_tree.update(visited_this_level)
82

83
        return visited_tree
84

85
    def getLadders(
86
        self, beginWord: str, endWord: str, wordTree: Dict[str, List[str]]
87
    ) -> List[List[str]]:
88
        """
89
        DFS traversal from endWord to beginWord in a given tree.
90
        """
91

92
        def dfs(node: str) -> List[List[str]]:
93
            if node == beginWord:
94
                return [[beginWord]]
95
            if node not in wordTree:
96
                return []
97

98
            res = []
99
            parents = wordTree[node]
100
            for parent in parents:
101
                res += dfs(parent)
102
            for r in res:
103
                r.append(node)
104
            return res
105

106
        return dfs(endWord)