剑指 Offer 12. 矩阵中的路径【DFS】

题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false

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

例如,在下面的 3×4 的矩阵中包含单词 "ABCCED"(单词中的字母已标出)。

img

示例 1:

输入:board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”
输出:true

示例 2:

输入:board = [[“a”,”b”],[“c”,”d”]], word = "abcd"
输出:false

提示:

1 <= board.length <= 200
1 <= board[i].length <= 200
board 和 word 仅由大小写英文字母组成

解题思路

利用深度优先搜索的方式进行,判断当前位置东南西北方向未访问的点的位置是否和下个字符串相同,如果有一个方向符合要求,那么就朝这个方向继续进行搜索。对不符合要求的方向进行剪枝操作。

其中运用回溯的思想进行对不符合要求的路径进行结点访问情况恢复。

代码

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
static class Solution12 {
int x[] = new int[]{0, 1, 0, -1};
int y[] = new int[]{1, 0, -1, 0};

public boolean exist(char[][] board, String word) {
if (board.length == 0 || board[0].length == 0) {
return false;
}
char[] arrayWord = word.toCharArray();
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == arrayWord[0]) {
visited[i][j] = true;
if (dfs(board, arrayWord, i, j, m, n, 1, visited)) {
return true;
}
visited[i][j] = false;
}
}
}
return false;
}

private boolean dfs(char[][] board, char[] arrayWord, int i, int j, int m, int n, int index, boolean[][] visited) {
if (index == arrayWord.length) {
return true;
}
int indexI = i, indexY = j;
boolean findPath = false;
for (int k = 0; k < 4; k++) {
indexI = i + x[k];
indexY = j + y[k];
if (indexI >= 0 && indexI < m && indexY >= 0 && indexY < n && !visited[indexI][indexY] && board[indexI][indexY] == arrayWord[index]) {//剪枝
visited[indexI][indexY] = true;
findPath = dfs(board, arrayWord, indexI, indexY, m, n, index + 1, visited);
if (findPath) {
return true;
} else {
visited[indexI][indexY] = false;
}
}
}
return findPath;
}
}

复杂度分析

注:复杂度分析参考官方题解。

时间复杂度:O($3^{length} MN$) ,length为查找字符串长度。

空间复杂度:O(MN) ,visited数组使用的空间

资源

https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/

https://leetcode-cn.com/problems/word-search/solution/dan-ci-sou-suo-by-leetcode-solution/

剑指 Offer 12. 矩阵中的路径【DFS】

http://example.com/2021/04/10/12 矩阵中的路径/

Author

John Doe

Posted on

2021-04-10

Updated on

2021-06-08

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.