Giả sử ta có bảng 2D và một từ, ta phải tìm xem từ có hiện diện trong lưới hay không. Từ có thể được tạo từ các chữ cái của ô liền kề theo trình tự, "liền kề" nghĩa là các ô ngang hoặc dọc. Không được dùng cùng một ô chữ cái hơn một lần. Ví dụ ma trận:
| A | B | C | E |
| S | F | C | S |
| A | D | E | F |
Với từ "ABCCED", trả về true; từ "SEE" trả về true; từ "ABCB" trả về false.
Các bước:
Giải quyết bằng đệ quy. Hàm đệ quy tên find(), nhận ma trận mat, từ word, hàng row, cột col, chỉ số i (ban đầu i=0).
Nếu i == độ dài word, trả về True.
Nếu row >= số hàng mat hoặc row < 0 hoặc col >= số cột mat hoặc col < 0 hoặc word[i] != mat[row][col], trả về False.
mat[row][col] := "*" (đánh dấu đã thăm).
res := find(mat, word, row+1, col, i+1) OR find(mat, word, row-1, col, i+1) OR find(mat, word, row, col+1, i+1) OR find(mat, word, row, col-1, i+1).
mat[row][col] := word[i] (khôi phục).
Trả về res.
Chương trình chính:
- n := số hàng, m := số cột.
- Với i từ 0 đến n-1, j từ 0 đến m-1:
- Nếu word[0] == mat[i][j] và find(mat, word, i, j) không False, trả về True.
Trả về False.
Ví dụ
class Solution(object):
def exist(self, board, word):
n = len(board)
m = len(board[0])
for i in range(n):
for j in range(m):
if word[0] == board[i][j]:
if self.tim_kiem(board, word, i, j):
return True
return False
def tim_kiem(self, board, word, hang, cot, i=0):
if i == len(word):
return True
if hang >= len(board) or hang < 0 or cot >= len(board[0]) or cot < 0 or word[i] != board[hang][cot]:
return False
board[hang][cot] = '*'
ket_qua = (self.tim_kiem(board, word, hang+1, cot, i+1) or
self.tim_kiem(board, word, hang-1, cot, i+1) or
self.tim_kiem(board, word, hang, cot+1, i+1) or
self.tim_kiem(board, word, hang, cot-1, i+1))
board[hang][cot] = word[i]
return ket_qua
ob1 = Solution()
print(ob1.exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "SEE"))
Đầu vào
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] "SEE"
Đầu ra
True