leetcode 79. 单词搜索

题解

递归,查看元素的上下左右位置,注意已经搜索过的位置,把搜索过的置为非字母,同时也不要忘了还原

示例代码(go)

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
func exist(board [][]byte, word string) bool {
for x := 0; x < len(board); x++ {
for y := 0; y < len(board[x]); y++ {
if dfs(board, word, x, y, 0) {
return true
}
}
}
return false
}

func dfs(board [][]byte, word string, x, y, i int) bool {
if i == len(word) {
return true
}
if x < 0 || y < 0 || x == len(board) || y == len(board[x]) {
return false
}
if board[x][y] != word[i] {
return false
}

board[x][y] ^= 255;
exists := dfs(board, word, x+1, y, i+1) || dfs(board, word, x-1, y, i+1) || dfs(board, word, x, y+1, i+1) || dfs(board, word, x, y-1, i+1)
board[x][y] ^= 255;
return exists
}