79.单词搜索
题解
思路：dfs，最近写dfs好顺，好喜欢写dfs。。。
代码
type pair struct {
x, y int
}
var dirs = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
func exist(board [][]byte, word string) bool {
flag := false
vis := make(map[pair]bool)
n, m := len(board), len(board[0])
var dfs func(x, y, idx int)
dfs = func(x, y, idx int) {
if word[idx] != board[x][y] {
return
}
if idx == len(word)-1 {
flag = true
return
}
vis[pair{x, y}] = true
for _, v := range dirs {
nx, ny := x+v.x, y+v.y
if nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[pair{nx, ny}] {
dfs(nx, ny, idx+1)
}
}
vis[pair{x, y}] = false
}
for i, v := range board {
for j := range v {
dfs(i, j, 0)
if flag {
return flag
}
}
}
return flag
}
