Giả sử chúng ta có một bảng 2D và một danh sách các từ. Vì vậy, từ từ điển, chúng ta phải tìm tất cả các từ trong bảng. Ở đây mỗi từ phải được xây dựng từ các chữ cái của ô liền kề tuần tự, trong đó các ô liền kề là các ô lân cận theo chiều ngang hoặc chiều dọc. Chúng ta phải lưu ý rằng không được sử dụng cùng một ô chữ cái nhiều lần trong một từ.
Vì vậy, nếu đầu vào giống như -
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
tạo một kết quả mảng
-
Xác định một phương thức có tên là giải quyết (), phương thức này sẽ đưa lên bảng, d, i, j s
-
khi i hoặc j không nằm trong phạm vi hàng và cột của bảng tương ứng, trả về false
-
l:=board [i, j]
-
nếu l có trong d, thì
-
d:=d [l], nối l với s
-
nếu # ở d và d [#] không phải là null thì
-
chèn s vào kết quả
-
đặt d [#]:=0
-
-
bảng [i, j]:=*
-
nếu i + 1
-
gọi giải quyết (board, d, i + 1, j, s)
-
-
nếu j + 1
-
gọi giải quyết (board, d, i, j + 1, s)
-
-
nếu i-1> 0 và lên [i - 1, j] ở d, thì
-
gọi giải quyết (board, d, i - 1, j, s)
-
-
nếu j-1> 0 và lên [i, j-1] ở d, thì
-
gọi giải quyết (board, d, i, j-1, s)
-
-
bảng [i, j]:=l
-
-
xác định một phương thức được gọi là insert (), phương thức này sẽ lấy từ và từ điển t
-
hiện tại:=t
-
cho tôi trong từ
-
nếu tôi không có trong hiện tại, thì hiện tại [i]:=bản đồ mới
-
current:=current [i]
-
-
hiện tại [#]:=1
-
Từ phương thức chính, hãy làm như sau -
-
tạo bản đồ t
-
cho từ trong từ:gọi chèn (từ, t)
-
cho mỗi ô i, j trong bảng - gọi giải quyết (board, t, i, j)
-
trả về kết quả
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class Solution(object):
def findWords(self, board, words):
self.result = []
t = {}
for word in words:
self.insert(word,t)
for i in range(len(board)):
for j in range(len(board[0])):
self.solve(board,t,i,j)
return self.result
def solve(self,board,d,i,j,s=""):
if i<0 or j<0 or i>=len(board) or j>=(len(board[0])):
return
l = board[i][j]
if l in d:
d = d[l]
s+=l
if "#" in d and d['#']:
self.result.append(s)
d['#'] = 0
board[i][j] = '*'
if i+1<len(board) and board[i+1][j] in d :
self.solve(board,d,i+1,j,s)
if j+1 < len(board[0]) and board[i][j+1] in d:
self.solve(board,d,i,j+1,s)
if i-1>=0 and board[i-1][j] in d :
self.solve(board,d,i-1,j,s)
if j-1>=0 and board[i][j-1] in d :
self.solve(board,d,i,j-1,s)
board[i][j] = l
def insert(self, word,t):
current = t
for i in word:
if i not in current:
current[i] = {}
current =current[i]
current['#']=1
ob = Solution()
print(ob.findWords([["o","a","a","n"],["e","t","e","a"],["i","h","k", "r"],["i","f","l","v"]],["oath","pea","tea","rain"])) Đầu vào
[["o","a","a","n"], ["e","t","e","a"], ["i","h","k","r"], ["i","f","l","v"]], ["oath","pea","tea","rain"]
Đầu ra
['oath', 'tea']