Python中的单词搜索

假设我们有一个2D板和一个单词，我们必须查找单词是否存在于网格中。单词可以由顺序相邻的单元格的字母组成，“相邻”单元格是水平或垂直相邻的单元格。我们不应多次使用同一个字母单元格。所以如果矩阵像-

给定单词“ ABCCED”，答案将是正确的，对于单词“ SEE”，它将是正确的，但是对于“ ABCB”，如果答案是错误的。

让我们看看步骤-

• 我们将使用递归方法解决此问题。因此，如果调用了递归方法名称find()，则需要矩阵矩阵，单词，行，列和索引i。最初，索引i = 0

• 如果i =字长，则返回True

• 如果row> = mat的行数或row <0或col> = mat的列数或col <0或word [i]与mat [row，col]不同，则返回false

• mat [row，col]：=“ *”

• res：= find（mat，word，row + 1，col，i +1）或find（mat，word，row-1，col，i + 1）或find（mat，word，row，col + 1，i + 1）或find（mat，word，row，col-1，i + 1）

• mat [row，col]：=单词[i]

• 返回资源

• 主要任务将像-

• n：=行数和m：=列数

• 当我的范围是0到n

• 如果word [0] = mat [i，j]

• 如果find(mat,word,i,j)不为假，则返回true

• 对于0到m范围内的j

让我们看下面的实现以更好地理解-

示例

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