题目概述
- 算法说明
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如
a b c e
s f c s
a d e e
矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
- 测试用例
输入：
[[a,b,c,e],
[s,f,c,s],
[a,d,e,e]],
“abcced”
输出：
true
输入：
[[a,b,c,e],
[s,f,c,s],
[a,d,e,e]],
“abcb”
输出：
false
备注：
0 <= matrix.length <= 200
0 <= matrix[i].length <= 200
解析&参考答案
- 解析
回溯法：
判断第一个字符有没有存在，满足三点就行：
①当前节点出界了
②这个格子已经走过了
③这个格子中的字符不是我们要找的
如果以上三点任意一点满足的话，就return false，否则这个格子就是我们要找的。
当该格子是要找的格子后，判断后面的格子，使用递归判断上下左右即可。只需要注意一点，如果某一个方向的格子不对，那就回溯，重新来过，判断其他方向。
- 参考答案
vim jz65.go
package main
import "fmt"
func HasPath(matrix [][]byte, word string) bool {
if len(matrix) == 0 || len(word) == 0 {
return false
}
rows := len(matrix)
columns := len(matrix[0])
visited := make([][]bool, rows)
for i := 0; i < rows; i++ {
visited[i] = make([]bool, columns)
}
for i := 0; i < rows; i++ {
for j := 0; j < columns; j++ {
if matrix[i][j] == word[0] {
if Backtrack(matrix, word, i, j, 0, &visited) {
return true
}
}
}
}
return false
}
func Backtrack(matrix [][]byte, word string, x, y, cur int, visited *[][]bool) bool {
if cur == len(word) {
return true
}
if x >= 0 && x < len(matrix) && y >= 0 && y < len(matrix[0]) && (*visited)[x][y] == false && matrix[x][y] == word[cur] {
(*visited)[x][y] = true
if Backtrack(matrix, word, x+1, y, cur+1, visited) || Backtrack(matrix, word, x, y+1, cur+1, visited) || Backtrack(matrix, word, x-1, y, cur+1, visited) || Backtrack(matrix, word, x, y-1, cur+1, visited) {
return true
}
(*visited)[x][y] = false
}
return false
}
func main() {
var arr = [][]byte{{'a', 'b', 'c', 'e'}, {'s', 'f', 'c', 's'}, {'a', 'd', 'e', 'e'}}
// str := "abcb" // false
str := "abcced" // true
// [[A,B,C,E,H,J,I,G],[S,F,C,S,L,O,P,Q],[A,D,E,E,M,N,O,E],[A,D,I,D,E,J,F,M],[V,C,E,I,F,G,G,S]],"SGGFIECVAASABCEHJIGQEM" //true
ret := HasPath(arr, str)
fmt.Println(ret)
}
注意事项
- 当某个方向的格子不符合要求的时候，需要回溯，然后找其它方向的格子。
说明
- 当前使用 go1.15.8
- 参考 牛客网--剑指offer
标题中jzn(n为具体数字)代表牛客网剑指offer系列第n号题目，例如 jz01 代表牛客网剑指offer中01号题目。
注意!!!
- 笔者最近在学习 golang，因此趁机通过数据结构和算法来进一步熟悉下go语言
- 当前算法主要来源于剑指 offer，后续会进一步补充 LeetCode 上重要算法，以及一些经典算法
- 此处答案仅为参考，不一定是最优解，欢迎感兴趣的读者在评论区提供更优解
