leetcode剑指 Offer 12. 矩阵中的路径

leetcode剑指 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 仅由大小写英文字母组成

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法1

这个题要我们判断二维数组board中是否存在字符串word的所有 如果只是这个要求,我们可以直接用哈希表来解决,但是它还增加了一个条件,就是字母之间必须相邻,,也就是说word[0]与word[1]在board数组中位置必须是相邻的,可以是行相邻,也可以是列相邻,(相差一个位置),这样哈希表需要储存出现的位置信息,后期的逻辑就变得比较复杂,1.判断不能重复使用,2.判断不能超出数组边界同时不能漏掉数据,3. 相邻的字母的在board数组中的位置必须相同,必须满足所有的判断条件,不断先后索引,直到word中所有字母都在board中出现并且满足条件返回ture,如果不满足其中任何一个条件,就搜索下一个board中word的首字母,直到完全没有一个路线可以将整个word所有字母走完,返回false

1. 遍历网格中的每个位置，如果某个位置的字符与单词的第一个字符相同，则从该位置开始进行搜索。

2. 在搜索的过程中，需要判断当前位置是否越界、是否已经被访问过以及是否与单词中对应位置的字符相同。

3. 如果搜索到单词的最后一个字符，则说明单词存在于网格中，返回 true。

4. 如果搜索到某个位置无法继续搜索（即无法与单词中对应位置的字符相匹配），则需要回溯到上一个位置重新进行搜索。

• 时间复杂度(O(n^2))
• 空间复杂度(O(n^2))

法2

• 时间复杂度(O())
• 空间复杂度(O())

法3

• 时间复杂度(O())
• 空间复杂度(O())

执行结果

法1

func exist(board [][]byte, word string) bool {
    m, n := len(board), len(board[0])
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if dfs(board, visited, i, j, word, 0) {
                return true
            }
        }
    }
    return false
}

func dfs(board [][]byte, visited [][]bool, i, j int, word string, k int) bool {
    if board[i][j] != word[k] {
        return false
    } else if k == len(word)-1 {
        return true
    }
    visited[i][j] = true
    defer func() { visited[i][j] = false }()
    if i > 0 && !visited[i-1][j] && dfs(board, visited, i-1, j, word, k+1) {
        return true
    }
    if i < len(board)-1