Giả sử chúng ta có một bảng chữ cái 4 x 4 và một danh sách các từ, chúng ta phải tìm số lượng từ lớn nhất có thể được tạo ra trong bảng bằng một dãy các chữ cái liền kề, sử dụng nhiều nhất một ô cho mỗi từ (nhưng chúng ta có thể sử dụng lại các ô cho các từ khác). Chúng ta có thể đi lên, xuống, sang trái, sang phải hoặc theo hướng chéo.
Vì vậy, nếu đầu vào giống như
| m | b | f | d |
| x | a | y | a |
| t | z | t | r |
| s | q | q | q |
words =["bat", "far", "mat"], thì đầu ra sẽ là 3, vì chúng ta có thể tạo ra mat [0,1] → [1,1] → [2,0], bat [0, 2] → [1,1] → [2,2] và xa [0,2] → [1,3] → [2,3].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
N:=số hàng của A, M:=số cột có kích thước của A
-
trie:=một bản đồ mới
-
đối với mỗi từ trong từ, hãy thực hiện
-
hiện tại:=trie
-
đối với mỗi c trong từ, hãy thực hiện
-
nếu c đang ở hiện tại thì
-
current:=current [c]
-
-
nếu không,
-
current [c]:=a new map
-
current:=current [c]
-
-
-
hiện tại ["*"]:=True
-
-
ans:=0
-
Định nghĩa một hàm dfs (). Điều này sẽ mất x, y, d
-
nếu "*" ở d, thì
-
loại bỏ d ["*"]
-
ans:=ans + 1
-
-
tạm thời:=A [x, y]
-
A [x, y]:="#"
-
đối với mỗi mục tôi trong [x - 1, x, x + 1], thực hiện
-
đối với mỗi mục j trong [y - 1, y, y + 1], thực hiện
-
nếu i và j trong phạm vi ma trận và A [i, j] nằm trong d, thì
-
dfs (i, j, d [A [i, j]])
-
-
-
-
A [x, y]:=temp
-
Từ phương thức chính, hãy làm như sau -
-
đối với tôi trong phạm vi từ 0 đến N, hãy thực hiện
-
đối với j trong phạm vi từ 0 đến M, thực hiện
-
nếu A [i] [j] ở trie thì
-
dfs (i, j, trie [A [i, j]])
-
-
-
-
trả lại ans
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
[ ["m", "b", "f", "d"], ["x", "a", "y", "a"], ["t", "z", "t", "r"], ["s", "q", "q", "q"] ], ["bat", "far", "mat"]
Đầu ra
3