题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。

如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。

注意：

输入的路径不为空；
所有出现的字符均为大写英文字母；

golang 代码

//优化点，可以直接将走过的路径替换为空，就可省略额外空间
var address = make([][]bool,100)

func hasPath(matrix [][]byte, str string) bool {
    for i := 0; i < 100; i++ {
        address[i] = make([]bool, 100)
    }
    for i := 0 ; i < len(matrix) ; i++ {
        for j := 0 ; j < len(matrix[i]) ; j++ {
            if find(matrix,i,j,0,str) {
                return true
            }
        }
    }
    return false
}

//i为横坐标，j为纵坐标，n为输入str的第几个（用于递归）
func find(matrix [][]byte, i int , j int , n int , str string ) bool {
    if matrix[i][j] != str[n] {
        return false
    }
    if n == len(str) - 1 {
        return true
    }
    address[i][j] = true
    n++
    //上下左右
    var x = []int{-1,1,0,0}
    var y = []int{0,0,-1,1}
    for k := 0 ; k < 4 ; k++ {
        a := i + x[k]
        b := j + y[k]
        if a >= 0 && a < len(matrix) && b >= 0 && b < len(matrix[0]) {
            if address[a][b] == false && find(matrix,a,b,n,str) {
                return true
            }
        }
    }
    address[i][j] = false
    return false
}