12. 矩阵中的路径

题目链接

牛客 (opens new window)

力扣 (opens new window)

题目描述

判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向上下左右移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。

例如下面的矩阵包含了一条 bfce 路径。

解题思路

思路就是使用DFS来找出是否有完整路径，

有几点需要注意：

1.每次使用过的值需要进行格式化，如赋值成' ',

2.需要注意的是,在使用深度搜索时，需要给定i,j的范围，不然会报错

3.k值的判断，最后判断是k == len(word)而不是k == len(word) - 1,因为无论如何，会进入深度搜索，导致k++一次，即使word中只有一个字符word[0],k也会变成1。

func exist(board [][]byte, word string) bool {
   m,n := len(board), len(board[0])
   for i := 0; i < m; i++ {
       for j := 0; j < n; j++ {
         //如果在数组中找得到第一个数，就执行下一步，否则返回false
         if search(board, i, j, 0,word) {
             return true
             }
        }
    }
    return false   
}
func search(board [][]byte, i,j,k int, word string) bool {
    //如果找到最后一个数，则返回true,搜索成功
    if k == len(word) {
        return true
    }
    //i,j的约束条件
    if i < 0 || j < 0 || i == len(board) || j == len(board[0]) {
        return false
    }

    //进入DFS深度优先搜索
    //先把正在遍历的该值重新赋值，如果在该值的周围都搜索不到目标字符，则再把该值还原
        //如果在数组中找到第一个字符，则进入下一个字符的查找
    if board[i][j] == word[k] {
        temp := board[i][j]
        board[i][j] = ' '
        //下面这个if语句，如果成功进入，说明找到该字符，然后进行下一个字符的搜索,直到所有的搜索都成功，
        //即k == len(word) - 1 的大小时，会返回true，进入该条件语句，然后返回函数true值。
        if search(board, i, j + 1, k + 1, word) || 
        search(board, i, j - 1, k + 1, word) || 
        search(board, i + 1, j, k + 1, word) ||
        search(board, i - 1, j, k + 1, word)  {
            return true
        }else {
        //没有找到目标字符，还原之前重新赋值的board[i][j]
            board[i][j] = temp
        }
        }

  
    return false
}