Python中的单词搜索

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

一种CË
小号FC小号
一种dËF

给定单词“ 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