剑指 Offer 12. 矩阵中的路径

题目描述

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

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

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

示例 1：

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出：true

示例 2：

输入：board = [[“a”,“b”],[“c”,“d”]], word = “abcd”
输出：false

提示：

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成

**注意：**本题与主站 79 题相同：https://leetcode-cn.com/problems/word-search/

解法一：递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


func exist(board [][]byte, word string) bool {
    h, w, n := len(board), len(board[0]), len(word)
    visited := make([][]bool, h)
    for i := 0; i < h; i++ {
        visited[i] = make([]bool, w)
    }
    dirs := [][2]int{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}
    var dfs func(i, j, idx int) bool
    dfs = func(i, j, idx int) bool {
        if word[idx] != board[i][j] {
            return false
        }
        if idx == n-1 {
            return true
        }
        visited[i][j] = true
        defer func() { visited[i][j] = false }()
        for k := 0; k < len(dirs); k++ {
            ni, nj := i+dirs[k][0], j+dirs[k][1]
            if ni < 0 || nj < 0 || ni >= h || nj >= w || visited[ni][nj] {
                continue
            }
            if dfs(ni, nj, idx+1) {
                return true
            }
        }
        return false
    }

    for i := 0; i < h; i++ {
        for j := 0; j < w; j++ {
            if dfs(i, j, 0) {
                return true
            }
        }
    }
    return false
}

另一种代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


func exist(board [][]byte, word string) bool {
    m, n := len(board), len(board[0])
    dirs := [][]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
    record := make(map[int]bool)
    var check func(i, j, k int) bool
    check = func(i, j, t int) bool {
        if board[i][j] != word[t] {
            return false
        }
        if t == len(word)-1 {
            return true
        }
        key := i*n + j
        record[key] = true
        defer func() { record[key] = false }()
        for _, dir := range dirs {
            ni := i + dir[0]
            nj := j + dir[1]
            if ni < 0 || ni >= m || nj < 0 || nj >= n {
                continue
            }
            tmp := ni*n + nj
            if !record[tmp] {
                if check(ni, nj, t+1) {
                    return true
                }
            }
        }
        return false
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if check(i, j, 0) {
                return true
            }
        }
    }
    return false
}