第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0079. 单词搜索

题目地址(79. 单词搜索)

题目描述

1
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
2
3
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
4
5
6
7
示例:
8
9
board =
10
[
11
['A','B','C','E'],
12
['S','F','C','S'],
13
['A','D','E','E']
14
]
15
16
给定 word = "ABCCED", 返回 true
17
给定 word = "SEE", 返回 true
18
给定 word = "ABCB", 返回 false
19
20
21
提示:
22
23
board 和 word 中只包含大写和小写英文字母。
24
1 <= board.length <= 200
25
1 <= board[i].length <= 200
26
1 <= word.length <= 10^3
Copied!

前置知识

  • 回溯

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

在 2D 表中搜索是否有满足给定单词的字符组合,要求所有字符都是相邻的(方向不限). 题中也没有要求字符的起始和结束位置。
在起始位置不确定的情况下,扫描二维数组,找到字符跟给定单词的第一个字符相同的,四个方向(上,下,左,右)分别 DFS 搜索, 如果任意方向满足条件,则返回结果。不满足,回溯,重新搜索。
举例说明:如图二维数组,单词:"SEE"
1
1. 扫描二维数组,找到board[1,0] = word[0],匹配单词首字母。
2
2. 做DFS(上,下,左,右 四个方向)
3
4
如下图:
Copied!
word search 1
起始位置(1,0),判断相邻的字符是否匹配单词下一个字符 E.
1
1. 标记当前字符(1,0)为已经访问过,board[1][0] = '*'
2
2. 上(0,0)字符为 'A' 不匹配,
3
3. 下(2,0)字符为 'A',不匹配,
4
4. 左(-1,0)超越边界,不匹配,
5
5. 右(1,1)字符 'F',不匹配
6
7
如下图:
Copied!
word search 2
由于从起始位置 DFS 都不满足条件,所以
1
1. 回溯,标记起始位置(1,0)为未访问。board[1][0] = 'S'.
2
2. 然后继续扫描二维数组,找到下一个起始位置(1,3)
3
4
如下图:
Copied!
word search 3
起始位置(1,3),判断相邻的字符是否匹配单词下一个字符 E.
1
1. 标记当前字符(1, 3)为已经访问过,board[1][3] = '*'
2
2. 上(0,3)字符为 'E', 匹配, 继续DFS搜索(参考位置为(0,3)位置DFS搜索步骤描述)
3
3. 下(2,3)字符为 'E',匹配, #2匹配,先进行#2 DFS搜索,由于#2 DFS搜索没有找到与单词匹配,继续DFS搜索(参考位置为(2,3)DFS搜索步骤描述)
4
4. 左(1,2)字符为 'C',不匹配,
5
5. 右(1,4)超越边界,不匹配
6
7
如下图:
Copied!
word search 4
位置(0,3)满足条件,继续 DFS,判断相邻的字符是否匹配单词下一个字符 E
1
1. 标记当前字符(0,3)为已经访问过,board[0][3] = '*'
2
2. 上 (-1,3)超越边界,不匹配
3
3. 下(1,3)已经访问过,
4
4. 左(0,2)字符为 'C',不匹配
5
5. 右(1,4)超越边界,不匹配
6
7
如下图
Copied!
word search 5
从位置(0,3)DFS 不满足条件,继续位置(2,3)DFS 搜索
1
1. 回溯,标记起始位置(0,3)为未访问。board[0][3] = 'E'.
2
2. 回到满足条件的位置(2,3),继续DFS搜索,判断相邻的字符是否匹配单词下一个字符 'E'
3
3. 上 (1,3)已访问过
4
4. 下(3,3)超越边界,不匹配
5
5. 左(2,2)字符为 'E',匹配
6
6. 右(2,4)超越边界,不匹配
7
8
如下图:
Copied!
word search 6
单词匹配完成,满足条件,返回 True.

复杂度分析

  • 时间复杂度: O(m*n) - m 是二维数组行数, n 是二维数组列数
  • 空间复杂度: O(1) - 这里在原数组中标记当前访问过,没有用到额外空间
注意:如果用 Set 或者是 boolean[][]来标记字符位置是否已经访问过,需要额外的空间 O(m*n).

关键点分析

  • 遍历二维数组的每一个点,找到起始点相同的字符,做 DFS
  • DFS 过程中,要记录已经访问过的节点,防止重复遍历,这里(Java Code 中)用 * 表示当前已经访问过,也可以用 Set 或者是 boolean[][]数组记录访问过的节点位置。
  • 是否匹配当前单词中的字符,不符合回溯,这里记得把当前 * 重新设为当前字符。如果用 Set 或者是 boolean[][]数组,记得把当前位置重设为没有访问过。

代码 (Java/Javascript/Python3)

Java Code
1
public class LC79WordSearch {
2
public boolean exist(char[][] board, String word) {
3
if (board == null || word == null) return false;
4
if (word.length() == 0) return true;
5
if (board.length == 0) return false;
6
int rows = board.length;
7
int cols = board[0].length;
8
for (int r = 0; r < rows; r++) {
9
for (int c = 0; c < cols; c++) {
10
// scan board, start with word first character
11
if (board[r][c] == word.charAt(0)) {
12
if (helper(board, word, r, c, 0)) {
13
return true;
14
}
15
}
16
}
17
}
18
return false;
19
}
20
21
private boolean helper(char[][] board, String word, int r, int c, int start) {
22
// already match word all characters, return true
23
if (start == word.length()) return true;
24
if (!isValid(board, r, c) ||
25
board[r][c] != word.charAt(start)) return false;
26
// mark visited
27
board[r][c] = '*';
28
boolean res = helper(board, word, r - 1, c, start + 1) // 上
29
|| helper(board, word, r + 1, c, start + 1) // 下
30
|| helper(board, word, r, c - 1, start + 1) // 左
31
|| helper(board, word, r, c + 1, start + 1); // 右
32
// backtracking to start position
33
board[r][c] = word.charAt(start);
34
return res;
35
}
36
37
private boolean isValid(char[][] board, int r, int c) {
38
return r >= 0 && r < board.length && c >= 0 && c < board[0].length;
39
}
40
}
Copied!
Python3 Code
1
class Solution:
2
def exist(self, board: List[List[str]], word: str) -> bool:
3
m = len(board)
4
n = len(board[0])
5
6
def dfs(board, r, c, word, index):
7
if index == len(word):
8
return True
9
if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[index]:
10
return False
11
board[r][c] = '*'
12
res = dfs(board, r - 1, c, word, index + 1) or dfs(board, r + 1, c, word, index + 1) or dfs(board, r, c - 1, word, index + 1) or dfs(board, r, c + 1, word, index + 1)
13
board[r][c] = word[index]
14
return res
15
16
for r in range(m):
17
for c in range(n):
18
if board[r][c] == word[0]:
19
if dfs(board, r, c, word, 0):
20
return True
21
return False
Copied!
Javascript Code from @lucifer
1
/*
2
* @lc app=leetcode id=79 lang=javascript
3
*
4
* [79] Word Search
5
*/
6
function DFS(board, row, col, rows, cols, word, cur) {
7
// 边界检查
8
if (row >= rows || row < 0) return false;
9
if (col >= cols || col < 0) return false;
10
11
const item = board[row][col];
12
13
if (item !== word[cur]) return false;
14
15
if (cur + 1 === word.length) return true;
16
17
// 如果你用hashmap记录访问的字母, 那么你需要每次backtrack的时候手动清除hashmap,并且需要额外的空间
18
// 这里我们使用一个little trick
19
20
board[row][col] = null;
21
22
// 上下左右
23
const res =
24
DFS(board, row + 1, col, rows, cols, word, cur + 1) ||
25
DFS(board, row - 1, col, rows, cols, word, cur + 1) ||
26
DFS(board, row, col - 1, rows, cols, word, cur + 1) ||
27
DFS(board, row, col + 1, rows, cols, word, cur + 1);
28
29
board[row][col] = item;
30
31
return res;
32
}
33
/**
34
* @param {character[][]} board
35
* @param {string} word
36
* @return {boolean}
37
*/
38
var exist = function (board, word) {
39
if (word.length === 0) return true;
40
if (board.length === 0) return false;
41
42
const rows = board.length;
43
const cols = board[0].length;
44
45
for (let i = 0; i < rows; i++) {
46
for (let j = 0; j < cols; j++) {
47
const hit = DFS(board, i, j, rows, cols, word, 0);
48
if (hit) return true;
49
}
50
}
51
return false;
52
};
Copied!

参考(References)

大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。