Python中用于从字母矩阵中计算生成单词个数的程序
假设我们有一个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]。
为了解决这个问题,我们将按照以下步骤进行 –
- N:A的行数,M:A的列数
-
trie:一个新映射
-
对于单词列表中的每个单词,执行以下操作
- current:trie
-
对于单词中的每个字符c,请执行以下操作
- 如果c在current中,则
-
current:= current[c]
-
否则,
-
current[c]:=一个新映射
-
current:= current[c]
-
current[“*”]:= True
-
ans:= 0
-
定义dfs()函数。这将获取x,y,d
-
如果d中存在“*”,则
- 删除d中的[“*”]
-
ans:= ans + 1
-
temp:= A[x, y]
-
A[x,y]:=“#”
li>
* 对于[x-1,x,x+1]中的每个项i,执行以下操作
* 对于[y-1,y,y+1]中的每个项j,执行以下操作
* 如果i和j在矩阵范围内并且A[i,j]在d中,则
* dfs(i,j,d[A[i,j]])
- A[x,y]:= temp
-
从主方法中进行以下操作 –
-
对于范围0到N中的i,执行以下操作
- 对于范围0到M中的j,执行以下操作:
- 如果A[i][j]在trie中,则
-
dfs(i,j,trie[A[i,j]])
- 对于范围0到M中的j,执行以下操作:
-
返回ans
更多Python相关文章,请阅读:Python 教程
示例(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