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