前言
猛起更新。
正文
问题来源
本问题来自leetcode上的79题。
问题描述
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
分析：
没有使用辅助空间，直接用特殊字符代表已访问。
func exist(board [][]byte, word string) bool {
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
if dfs(board, word, i, j, 0) {
return true
}
}
}
return false
}
func dfs(board [][]byte, word string, i, j, index int) bool {
if index == len(word) {
return true
}
if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) {
return false
}
if board[i][j] != word[index] {
return false
}
board[i][j] = 0
if dfs(board, word, i-1, j, index+1) {
return true
}
if dfs(board, word, i, j-1, index+1) {
return true
}
if dfs(board, word, i+1, j, index+1) {
return true
}
if dfs(board, word, i, j+1, index+1) {
return true
}
board[i][j] = word[index]
return false
}
总结：
勤思考。
结语
不管怎么样好好加油。
