剑指 Offer 12. 矩阵中的路径
文章目录

题目

给定一个二维网格和一个单词, 找出该单词是否存在于网格中.

单词必须按照字母顺序, 通过相邻的单元格内的字母构成, 其中“相邻”单元格是那些水平相邻或垂直相邻的单元格. 同一个单元格内的字母不允许被重复使用.

示例:

1
2
3
4
5
6
board =
[
['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E']
]

给定 word = “ABCCED”, 返回 true
给定 word = “SEE”, 返回 true
给定 word = “ABCB”, 返回 false

提示:

1
2
3
4
board 和 word 中只包含大写和小写英文字母.
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

以下两个题目都是相同的:

题解

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
var found;
var exist = function (board, searchWord) {
const candidateStart = [];
found = false;
/* 先从迷宫中找到所有可能的出发点 */
board.map((row, i) => {
row.map((e, j) => {
if (e === searchWord[0]) {
candidateStart.push([i, j]);
}
});
});

/* 循环从每一个出发点开始寻路 */
candidateStart.map((start) => search(start, board, searchWord, 1));

return found;
};

var search = (start, board, searchWord, wordIndex) => {
/* 每次进入这个函数,那就预示着当前坐标单词已经匹配 */
if (found) return false;

let [x, y] = start;

/* 暂时保存这个位置原来的数据 */
const tmp = board[x][y];
/* 标记这个位置已访问过。 */
board[x][y] = "+";

const searchChar = searchWord[wordIndex];

/* 如果已经处理到最后一个单词 */
if (wordIndex === searchWord.length) {
found = true;
}
if (x > 0 && board[x - 1][y] === searchChar)
if (search([x - 1, y], board, searchWord, wordIndex + 1))
// 上
return true;
if (x < board.length - 1 && board[x + 1][y] === searchChar)
if (search([x + 1, y], board, searchWord, wordIndex + 1))
//下
return true;
if (y > 0 && board[x][y - 1] === searchChar)
if (search([x, y - 1], board, searchWord, wordIndex + 1))
//左
return true;
if (y < board[0].length - 1 && board[x][y + 1] === searchChar)
if (search([x, y + 1], board, searchWord, wordIndex + 1))
// 右
return true;

/* 将当前位置原来的数据给恢复回来, 如果不这样, 多次回溯的board将会相互影响 */
board[x][y] = tmp;

return false;
};