LeetCode 79. 单词搜索 | Python

79. 单词搜索

---

题目来源：https://leetcode-cn.com/problems/word-search

题目

---

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

提示：

• board 和 word 中只包含大写和小写英文字母。
• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• 1 <= word.length <= 10^3

解题思路

---

思路：深度优化搜索、回溯

首先看题意，题目中要求单词必须按照字母顺序，在给定的二维数组中，找到单词。可通过相邻单元格的字母组成，这里【相邻】包括横向和纵向相邻的单元格，这里就涉及到一个偏移量的问题，但是同一个单元的字母不能够重复使用。

先看下如何去实现搜索？首先我们要先要对二维数组进行遍历，要先找到跟单词首字母相同的元素，这里要注意，当找到这个元素时，要先进行标记，因为题意要求字母不能重复使用。

当找到这个元素时，从当前元素的位置开始进行搜索，需要往四个方位进行搜索，看看相邻的单元格元素是否是单词的下一个字母，这里分为两种情况：

• 能够匹配时，从这个元素继续进行搜索
• 不能匹配时，返回 False，这里要进行回溯

当所有的字母完全匹配时，则返回 True。

具体的实现代码如下。

代码实现

---

class Solution:
    directions = [(1, 0), (0, -1), (-1, 0), (0, 1)]

    def exist(self, board: List[List[str]], word: str) -> bool:
        if len(board) == 0:
            return False
        
        # 四个方位偏移量
        

        rows = len(board)
        cols = len(board[0])

        # 这里用以标记元素是否使用
        # False 表示未使用
        # True 表示已使用
        marked = [[False for _ in range(cols)] for _ in range(rows)]

        # 先遍历，
        for row in range(rows):
            for col in range(cols):
                    # 当找到所有元素时返回 True
                    if self._search(row, col, board, word, 0, marked):
                        return True
        return False

    def _search(self, i, j, board, word, index, marked):
        # 终止条件
        if index == len(word) - 1:
            return board[i][j] == word[index]

        # 只有匹配了才继续搜索
        if board[i][j] == word[index]:
            # 这里先标记元素，如果搜索不成功的情况下，解除标记
            marked[i][j] = True
            # 四个方位搜索
            for dx, dy in self.directions:
                nrow = i + dx
                ncol = j + dy

                # 限定边界，
                # 搜索时找相邻未使用过的元素
                if 0 <= nrow < len(board) and 0 <= ncol < len(board[0]) and not marked[nrow][ncol] and self._search(nrow, ncol, board, word, index + 1, marked):
                    return True
            # 释放标记
            marked[i][j] = False
        return False

实现结果

---

实现结果

总结

---

• 使用深度优先搜索 + 回溯的思路，解决此题；
• 首先定位单词首元素，找到对应的位置之后，由此从四个方位继续搜索；
• 搜索的同时，要先标记当前元素为已使用，防止后面定位的元素搜索时重复使用；
• 如果某个搜索路线未找到单词时，要进行回溯，将此次标记的元素全部释放。

---

欢迎关注微信公众号《书所集录》