Tìm kiếm từ bằng Python

Giả sử chúng ta có một bảng 2D và một từ, chúng ta phải tìm xem từ đó có trong lưới hay không. Các từ có thể được tạo từ các chữ cái của ô liền kề theo thứ tự, 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 không nên sử dụng cùng một ô chữ cái nhiều hơn một lần. Vì vậy, nếu ma trận giống như -

Các từ cho trước được nói là "ABCCED", câu trả lời sẽ là đúng, đối với từ "XEM", nó sẽ là đúng, nhưng đối với "ABCB", nếu sẽ là sai.

Hãy để chúng tôi xem các bước -

• Chúng tôi sẽ giải quyết vấn đề này bằng cách sử dụng phương pháp đệ quy. Vì vậy, nếu tên phương thức đệ quy được gọi là find (), điều này sẽ nhận mat ma trận, từ, hàng, col và chỉ mục i. Ban đầu chỉ số i =0
• nếu i =độ dài của các từ, thì trả về True
• nếu row> =số hàng của mat hoặc row <0 hoặc col> =col count of mat hoặc col <0 hoặc word [i] không giống với mat [row, col], thì trả về false
• mat [row, col]:=“*”
• res:=find (mat, word, row + 1, col, i + 1) hoặc find (mat, word, row - 1, col, i + 1) hoặc find (mat, word, row, col + 1, i + 1) hoặc tìm (mat, word, row, col - 1, i + 1)
• mat [row, col]:=word [i]
• trả lại res
• Nhiệm vụ chính sẽ được thực hiện như -
• n:=số hàng và m:=số cột
• cho tôi trong phạm vi từ 0 đến n
  • cho j trong phạm vi từ 0 đến m
    • if word [0] =mat [i, j]
      • nếu find (mat, word, i, j) không sai thì trả về true

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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.find(board,word,i,j):
                  return True
      return False
   def find(self, board,word,row,col,i=0):
      if i== len(word):
         return True
      if row>= len(board) or row <0 or col >=len(board[0]) or col<0 or word[i]!=board[row][col]:
         return False
      board[row][col] = '*'
      res = self.find(board,word,row+1,col,i+1) or self.find(board,word,row-1,col,i+1) or self.find(board,word,row,col+1,i+1) or self.find(board,word,row,col-1,i+1)
      board[row][col] = word[i]
      return res
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