Python程序计算我们可以从字母矩阵生成的单词数
假设我们有一个4x4的字母板和一个单词列表，我们必须找到可以由一系列相邻字母在面板中生成的单词数量最多，每个单词最多使用一个单元格（但是我们可以重用单元格来换句话说）。我们可以向上，向下，向左，向右或对角线方向移动。
所以，如果输入像
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]。
范例(Python)
让我们看下面的实现以更好地理解-
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