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]])

• 返回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