Python中用于从字母矩阵中计算生成单词个数的程序

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程