LeetCode-79. 单词搜索 - sheep44044的小站

回溯#

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

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

示例 1：

1
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"
2
输出：true

示例 2：

1
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE"
2
输出：true

示例 3：

1
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB"
2
输出：false

思路

感觉这道题是 200. 岛屿数量 的进阶版，难点就是如何处理四个方向的递归？

这里就给backtrack引入了一个bool返回值，这段代码found := backtrack(row-1, col, index+1) || backtrack(row+1, col, index+1) || backtrack(row, col-1, index+1) || backtrack(row, col+1, index+1)是点精之笔

并且这里对数据的存储和处理也是比较有意思的，board[row][col] = '#'，不需要引入额外的数组，就可以避开这个数

1
func exist(board [][]byte, word string) bool {
2
    m, n := len(board), len(board[0])
3

4
    var backtrack func(row, col, index int) bool
5
    backtrack = func(row, col, index int) bool {
6
        if index == len(word) {
7
            return true
8
        }
9

10
        if row < 0 || col < 0 || row >= m || col >= n || board[row][col] != word[index] {
11
            return false
12
        }
13

14
        temp := board[row][col]
15
        board[row][col] = '#'
16

17
        found := backtrack(row-1, col, index+1) || backtrack(row+1, col, index+1) || backtrack(row, col-1, index+1) || backtrack(row, col+1, index+1)
18

19
        board[row][col] = temp
20
        return found
21
    }
22

23
    for i := 0; i < m; i++ {
24
        for j := 0; j < n; j++ {
25
            if board[i][j] == word[0] {
26
                if backtrack(i, j, 0) {
27
                    return true
28
                }
29
            }
30
        }
31
    }
32
    return false
33
}