79. 单词搜索

Difficulty
Medium
Tags
回溯
URL
https://leetcode-cn.com/problems/word-search/
Star
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
notion imagenotion image
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
notion imagenotion image
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
示例 3：
notion imagenotion image
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
提示：
  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和 word 仅由大小写英文字母组成
进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
通过次数225,465提交次数491,734

法1 dfs

思路
先找到一个入口，然后从该入口向下一层查找，每一层有上下左右四个选项。
切记找到及时返回True。
题解
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        used = [[False] * len(board[0]) for _ in range(len(board))]
        # 先找到单词入口
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0]:
                    # 找到一个入口就可以往下查找了,如果当前入口不行再换一个入口。
                    used[i][j] = True
                    # 只要有一个入口可以， 就可以返回 True
                    if self.dfs(board=board, word=word, start=0, row=i, col=j, used=used):  
                        return True
                    used[i][j] = False
        # 所有入口都不行，或者没有入口 返回False
        return False

    def dfs(self, board, word, start, row, col, used):
        # 在 board[row][col] 位置找到了 word[start] 字符
        # 这一层从当前位置出发找下一个字符
        if start >= len(word)-1:
            return True

        # 向下
        if row+1 < len(board) and board[row+1][col] == word[start+1] and used[row+1][col] is False:
            used[row+1][col] = True
            if self.dfs(board, word, start+1, row+1, col, used):
                return True
            used[row+1][col] = False

        # 向上
        if row-1 >= 0 and board[row-1][col] == word[start+1] and used[row-1][col] is False:
            used[row-1][col] = True
            if self.dfs(board, word, start+1, row-1, col, used):
                return True
            used[row-1][col] = False

        # 向右
        if col+1 < len(board[0]) and board[row][col+1] == word[start+1] and used[row][col+1] is False:
            used[row][col+1] = True
            if self.dfs(board, word, start+1, row, col+1, used):
                return True
            used[row][col+1] = False

        # 向左
        if col-1 >= 0 and board[row][col-1] == word[start+1] and used[row][col-1] is False:
            used[row][col-1] = True
            if self.dfs(board, word, start+1, row, col-1, used):
                return True
            used[row][col-1] = False

        return False
一种更优雅的写法
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if len(board) == 0 or len(board[0]) == 0 or len(word) ==0:
            return False
        used = [[False]*len(board[0]) for _ in range(len(board))]
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0]:
                    if self.backtrack(board=board, word=word, i=i, j=j, used=used, start=0):
                        return True

        return False

    def backtrack(self, board, word, i, j, used, start):
        if start >= len(word):
            return True
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
            return False
        if used[i][j]:
            return False
        if board[i][j] != word[start]:
            return False

        used[i][j] = True

        res = self.backtrack(board, word, i+1, j, used, start+1) or \
                self.backtrack(board, word, i-1, j, used, start+1) or\
                self.backtrack(board, word, i, j+1, used, start+1) or \
                self.backtrack(board, word, i, j-1, used, start+1)
        used[i][j] = False

        return res