Python中的單詞搜尋

---

在Python中，**單詞搜尋**指的是確定給定單詞是否存在於網格中，這可以使用各種方法來完成，例如深度優先搜尋 (DFS) 方法和**回溯**演算法等，並且給定的單詞可以透過順序連線水平或垂直方向上的**相鄰**單元格來形成。

步驟

在Python中執行單詞搜尋所涉及的步驟如下。

• 考慮輸入棋盤（二維網格）

• 定義類和**exist()**方法的實現，該方法遍歷每個單元格

• 實現**find()方法**，遞迴地檢查可能的方向。

• 執行

輸入棋盤

讓我們考慮一個二維棋盤和一個單詞，我們必須找到它是否存在於網格中。例如，如果輸入單詞是“SEE”，它將返回**true**。

A	B	C	E
S	F	C	S
A	D	E	F

類定義和Exist方法

類**Word_Search**封裝了單詞搜尋問題的邏輯，**exist()**方法檢查單詞是否存在於棋盤中。

定義類

class Word_Search(object):

exist()方法

在下面的函式中，**'n'**和**'m'**分別表示二維網格的行數和列數。此方法使用兩個巢狀迴圈迭代棋盤中的每個單元格。

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

Find方法的初始化

**find()**方法遞迴地匹配從給定單元格**(row, col)**開始的單詞字元。

find()方法

在下面的函式中，**i**指的是（單詞中當前字元的索引）等於單詞的長度。如果整個單詞成功匹配，則返回**True**；如果條件失敗，則函式返回**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

執行

在最後一步，建立**Word_Search**類的例項。使用二維棋盤和單詞“SEE”呼叫**exist**方法，根據條件（給定單詞是否存在）列印'True'或'False'。

ob1 = Solution()
print(ob1.exist([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "SEE"))

示例

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"))

輸入

[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
"SEE"

輸出

True