資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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 := 一個新的對映
對於 words 中的每個單詞，執行以下操作：
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] := "#"
對於 [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）
讓我們看一下以下實現，以便更好地理解：
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
215 次瀏覽
