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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// @Title: 单词搜索 (Word Search)
// @Author: 15816537946@163.com
// @Date: 2020-06-25 07:15:36
// @Runtime: 4 ms
// @Memory: 3.4 MB
/*
 * @lc app=leetcode.cn id=79 lang=golang
 *
 * [79] 单词搜索
 *
 * https://leetcode-cn.com/problems/word-search/description/
 *
 * algorithms
 * Medium (38.96%)
 * Likes:    209
 * Dislikes: 0
 * Total Accepted:    19.6K
 * Total Submissions: 50.3K
 * Testcase Example:  '[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]\n"ABCCED"'
 *
 * 给定一个二维网格和一个单词,找出该单词是否存在于网格中。
 *
 * 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 *
 * 示例:
 *
 * board =
 * [
 * ⁠ ['A','B','C','E'],
 * ⁠ ['S','F','C','S'],
 * ⁠ ['A','D','E','E']
 * ]
 *
 * 给定 word = "ABCCED", 返回 true.
 * 给定 word = "SEE", 返回 true.
 * 给定 word = "ABCB", 返回 false.
 *
 */

// dfs+ 回溯
func exist(board [][]byte, word string) bool {
	if word == "" {
		return false
	}

	m := len(board)
	if m == 0 {
		return false
	}

	n := len(board[0])
	if n == 0 {
		return false
	}

	var dfs func(int, int, int) bool
	dfs = func(r, c, index int) bool {
		if len(word) == index {
			return true
		}

		if r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word[index] {
			return false
		}
		// 先update当前的状态, 防止步骤回退
		temp := board[r][c]
		board[r][c] = 0
		// 遍历四个方向
		if dfs(r+1, c, index+1) ||
			dfs(r-1, c, index+1) ||
			dfs(r, c+1, index+1) ||
			dfs(r, c-1, index+1) {
			return true
		}
		board[r][c] = temp

		return false
	}

	for i := range board {
		for j := range board[0] {
			if dfs(i, j, 0) {
				return true
			}
		}
	}

	return false

}