1
class Solution:
2
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
3
        solution = set()
4
        trie = self.make_trie(words)
5
        visited = set()
6
        for i in range(len(board)):
7
            for j in range(len(board[0])):
8
                self.dfs(i, j, board, trie, visited, "", solution)
9
        return solution
10

11
    def dfs(self, i, j, board, trie, visited, word, solution):
12
        if "*" in trie:
13
            if len(trie.keys()) == 0:
14
                return
15
            else:
16
                solution.add(word)
17
                del trie["*"]
18
        if (i, j) in visited:
19
            return
20
        if i < 0 or i == len(board) or j < 0 or j == len(board[0]):
21
            return
22
        if board[i][j] not in trie:
23
            return
24
        if len(trie[board[i][j]]) == 0:
25
            del trie[board[i][j]]
26
            return
27
        visited.add((i, j))
28
        neighbours = [(i, j - 1), (i - 1, j), (i, j + 1), (i + 1, j)]
29
        for n_x, n_y in neighbours:
30
            self.dfs(
31
                n_x,
32
                n_y,
33
                board,
34
                trie[board[i][j]],
35
                visited,
36
                word + board[i][j],
37
                solution,
38
            )
39
        visited.remove((i, j))
40

41
    def make_trie(self, words):
42
        trie = {}
43
        for word in words:
44
            current = trie
45
            for char in word:
46
                if char not in current:
47
                    current[char] = {}
48
                current = current[char]
49
            current["*"] = "*"
50
        return trie