from collections import defaultdict
class Trie:
def __init__(self):
self.children = defaultdict(Trie)
self.word = ""
def insert(self, word):
cur = self
for c in word:
cur = cur.children[c]
cur.word = word
主逻辑代码：
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
def dfs(row, col, cur):
if row < 0 or row >= m or col < 0 or col >= n or board[row][col] == '.' or board[row][col] not in cur.children: return
c = board[row][col]
cur = cur.children[c]
if cur.word != '': ans.add(cur.word)
board[row][col] = '.'
dfs(row+1,col, cur)
dfs(row-1,col, cur)
dfs(row,col+1, cur)
dfs(row,col-1, cur)
board[row][col] = c
m, n = len(board), len(board[0])
ans = set()
trie = Trie()
words = set(words)
for word in words:
trie.insert(word)
for i in range(m):
for j in range(n):
dfs(i, j, trie)
return list(ans)
