剑指 Offer 12. 矩阵中的路径

题意

在矩阵中寻找字符串路径，路径不能交叉，路径入口不指定

题解

思路：DFS，遍历矩阵寻找入口，步长确定作为成功条件，边界与字符串是否相等作为回溯条件，注意剪枝优化是将相等的位置置为空字符串，避免重复进入，结束后需要重新换回来

  • 时间复杂度：O(3^K MN) —— K表示字符串长度，最差情况遍历整个矩阵MN
  • 空间复杂度：O(K) —— 递归深度最大为字符串长度K ```go func exist(board [][]byte, word string) bool { for i := 0; i < len(board); i++ {
    1.   for j := 0; j <= len(board[0]); j++ {
    2.       if dfs(i, j, 0, board, word) {
    3.           return true
    4.       }
    5.   }
    } return false }

func dfs(i, j, step int, board [][]byte, word string) bool { if len(word) == step { return true }

if i < 0 || j < 0 || i == len(board) || j == len(board[0]) || board[i][j] != word[step] {
    return false
}

board[i][j] = ' '
res := dfs(i+1, j, step+1, board, word) || dfs(i, j+1, step+1, board, word) || dfs(i-1, j, step+1, board, word) || dfs(i, j-1, step+1, board, word)
board[i][j] = word[step]
return res

} ``` 结果：

  • 执行用时：4 ms, 在所有 Go 提交中击败了96.63%的用户
  • 内存消耗：3.2 MB, 在所有 Go 提交中击败了88.76%的用户