Python 中的单词搜索

假设我们有一个 2D 棋盘和一个单词，我们必须找出该单词是否存在于网格中。单词可以由连续相邻单元格的字母组成，"相邻"单元格是水平或垂直相邻的单元格。我们不应该多次使用相同的字母单元格。因此，如果矩阵类似于 −

给定单词"ABCCED"，答案将为真，对于单词"SEE"，答案将为真，但对于"ABCB" if 将为 false。

让我们看看步骤 −

• 我们将使用递归方法解决这个问题。因此，如果递归方法名称为 find()，则需要矩阵 mat、word、row、col 和索引 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) or find(mat, word, row - 1, col, i + 1) or find(mat, word, row, col + 1, i + 1) or find(mat, word, row, col - 1, i + 1)
• mat[row, col] := word[i]
• 返回 res
• 主要任务将像 − 一样执行
• n := 行数和 m := 列数
• for i in range 0 to n
  • for j in range 0 to m
    • if word[0] = mat[i, j]
      • 如果 find(mat, word, i, j) 不为 false，则返回 true

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

示例

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

相关文章

• Python 中通过 K 扩展列表
• Python - 使用交替的 0 和 1 初始化列表
• Python 中元组列表到字典的转换
• Python - 从两个列表中配对，使得成对的元素不相同
• 使用 Python 和 SQLite 的 SQL
• 使用 pytrie 模块在 Python 中进行前缀匹配
• 创建和访问 Python 包
• 如何使用正则表达式和数据类型选择多个 DataFrame 列
• 如何在 Pandas 中查找和过滤重复行?
• 用 Python 编写程序以正确的顺序查找机场?

有用资源

• python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/