单词搜索

1. 题目描述

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

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

2. 思路

1. 思路一
   • DFS，类似于岛屿数量.md，这里没法用memo记忆化的原因在于是暴力穷举？

3. 实现

3.1. DFS

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

    // 这里得遍历所有元素
    for i := range board {
        for j := range board[i] {
            if board[i][j] == word[0]{
                if existDFS(board, word, 0, i, j, len(board), len(board[0]), visited) {
                    return true
                }
            }
        }
    }
    return false
}


func existDFS(board [][]byte, word string, index, row, col, maxRow, maxCol int, visited [][]bool) bool {
    if index >= len(word) {return true}
    if row < 0 || row >= maxRow || col < 0 || col >= maxCol {return false}
    if visited[row][col] {return false}
    if word[index] == board[row][col] {
        visited[row][col] = true
        if isExists := existDFS(board, word, index+1, row+1, col, maxRow, maxCol, visited) ||
            existDFS(board, word, index+1, row-1, col, maxRow, maxCol, visited) ||
            existDFS(board, word, index+1, row, col+1, maxRow, maxCol, visited) ||
            existDFS(board, word, index+1, row, col-1, maxRow, maxCol, visited); isExists {
                return true
            }
        visited[row][col] = false
    }
    return false
}

4. 参考

• 79. 单词搜索 - 力扣（LeetCode）