假设我们有一个4 x 4的字母板和一个单词列表，我们必须找到可以由一系列相邻字母在面板中生成的单词数量最多，每个单词最多使用一个单元格（但是我们 可以重用单元格来换句话说）。 我们可以向上，向下，向左，向右或对角线方向移动。
所以，如果输入像
| m | b | f | d |
| x | a | y | a |
| t | z | t | r |
| s | q | q | q |
words = [“ bat”，“ far”，“ mat”]，则输出将为3，因为我们可以生成mat [0,1]→[1,1]→[2,0]，bat [0， 2]→[1,1]→[2,2]，far [0,2]→[1,3]→[2,3]。
让我们看下面的实现以更好地理解-
class Solution: def solve(self, A, words): N = len(A) M = len(A[0]) trie = dict() for word in words: current = trie for c in word: if c in current: current = current[c] else: current[c] = dict() current = current[c] current["*"] = True ans = 0 def dfs(x, y, d): nonlocal ans if "*" in d: del d["*"] ans += 1 temp = A[x][y] A[x][y] = "#" for i in [x - 1, x, x + 1]: for j in [y - 1, y, y + 1]: if 0 <= i < N and 0 <= j < M and A[i][j] in d: dfs(i, j, d[A[i][j]]) A[x][y] = temp for i in range(N): for j in range(M): if A[i][j] in trie: dfs(i, j, trie[A[i][j]]) return ans ob = Solution() matrix = [ ["m", "b", "f", "d"], ["x", "a", "y", "a"], ["t", "z", "t", "r"], ["s", "q", "q", "q"] ] words = ["bat", "far", "mat"] print(ob.solve(matrix, words))
[ ["m", "b", "f", "d"], ["x", "a", "y", "a"], ["t", "z", "t", "r"], ["s", "q", "q", "q"] ], ["bat", "far", "mat"]
输出结果
3