1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| // @Title: 矩阵中的路径 (矩阵中的路径 LCOF)
// @Author: 15816537946@163.com
// @Date: 2022-02-16 00:29:51
// @Runtime: 4 ms
// @Memory: 3.1 MB
func exist(board [][]byte, word string) bool {
m,n := len(board), len(board[0])
var dfs func(i,j,idx int) bool
dfs = func(i,j,idx int) bool {
if i <0 || i>=m || j<0 || j>=n || board[i][j] != word[idx] {
return false
}
if idx == len(word)-1 {
return true
}
board[i][j] = ' '
res := dfs(i+1,j,idx+1) || dfs(i-1,j,idx+1) || dfs(i,j+1, idx+1) || dfs(i,j-1,idx+1)
board[i][j] = word[idx]
return res
}
for i := range board {
for j := range board[0] {
if dfs(i,j,0) {
return true
}
}
}
return false
}
|