79. 单词搜索(Medium)

题目描述

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

样例

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

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

题解

本题是常见的 图 的搜索问题，使用深度搜索 。因为我们需要退回上一个节点状态，所以需要使用回溯法，记录和恢复状态。使用 visited 数组标记节点是否走过。

Python示例

def dfs(board, word, visited, r, c):
    if not word: # 找到
        return True

    direction = [-1, 0, 1, 0, -1]
    for d in range(4):
        i = r + direction[d]
        j = c + direction[d + 1]
        if 0<= i < len(board) and \
           0<= j < len(board[0]) and \
           board[i][j] == word[0] and \
           not visited[i][j]: # 未访问过
             visited[i][j] = 1
             if dfs(board, word[1:], visited, i, j): return True # 剪枝：找到答案
             visited[i][j] = 0
    return False # 遍历完仍未找到
         
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0]:
                    visited = [[0] * len(board[0]) for _ in range(len(board))]
                    visited[i][j] = 1
                    if dfs(board, word[1:], visited, i, j):
                        return True 
        return False

同样，判断是否符合规则的代码可以放在 DFS 的开头，这样代码稍微变一下。

def dfs(board, word, visited, r, c):
    if not word: # 找到
        return True
    if r < 0 or r >= len(board) or c < 0 or c >= len(board[0]) \
       or visited[r][c] \
       or board[r][c] != word[0]: 
           return False  
    
    direction = [-1, 0, 1, 0, -1]
    visited[r][c] = 1
    for d in range(4):
        i = r + direction[d]
        j = c + direction[d + 1]
        if dfs(board, word[1:], visited, i, j): 
            return True # 剪枝：找到答案
    visited[r][c] = 0
    return False # 遍历完仍未找到
         
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        visited = [[0] * len(board[0]) for _ in range(len(board))]
        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(board, word, visited, i, j):
                    return True 
        return False 

Go 示例

	func dfs(board [][]byte, word string, visited [][]bool, r, c int) bool {
    if len(word) == 0 {
        return true
    }
    if r < 0 || r >= len(board) || c < 0 || c >= len(board[0]) ||
       board[r][c] != word[0] || visited[r][c] {
           return false
    }

    visited[r][c] = true 
    directions := []int {-1, 0, 1, 0, -1}
    for d := 0; d < 4; d ++ {
        x := r + directions[d]
        y := c + directions[d + 1]
        if dfs(board, word[1:], visited, x, y) {
            return true
        }
    }
    visited[r][c] = false
    return false
}

func exist(board [][]byte, word string) bool {
    n, m := len(board), len(board[0])
    visited := make([][]bool, n)
    for i := range visited {
        visited[i] = make([]bool, m)
    }

    for i := 0; i < n; i ++ {
        for j := 0; j < m; j ++ {
            if dfs(board, word, visited, i, j) {
                return true
            }
        }
    }
    return false
}