友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
212. 单词搜索 II
给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。
单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例 1：
输入：board = [["o","a","a","n"],
["e","t","a","e"],
["i","h","k","r"],
["i","f","l","v"]],
words = ["oath","pea","eat","rain"]
输出：["eat","oath"]
示例 2：
输入：board = [["a","b"],
["c","d"]],
words = ["abcb"]
输出：[]
提示：
-
m == board.length -
n == board[i].length -
1 <= m, n <= 12 -
board[i][j]是一个小写英文字母 -
1 <= words.length <= 3 * 104 -
1 <= words[i].length <= 10 -
words[i]由小写英文字母组成 -
words中的所有字符串互不相同
思路分析
回溯：先根据首字母对单词进行分类，再遍历矩阵，找出首字母对应的坐标点。再对单词列表和坐标点进行回溯匹配。通过 43 / 65 个测试用例，后超时！
利用前缀树+回溯，可以避免重复判断单词相同的前缀部分，可以节省大量的计算。
-
一刷
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
/**
* 回溯+前缀树
* <p>
* 优化前，利用回溯，通过 43 / 65 个测试用例。超时！
*
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-12 22:53:03
*/
int[][] options = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public List<String> findWords(char[][] board, String[] words) {
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
Set<String> result = new HashSet<>();
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[r].length; c++) {
dfs(board, r, c, trie, result);
}
}
return new ArrayList<>(result);
}
private void dfs(char[][] board, int row, int col,
Trie trie, Set<String> result) {
if (row < 0 || row >= board.length
|| col < 0 || col >= board[0].length) {
return;
}
char letter = board[row][col];
if (!trie.containsLetter(letter)) {
return;
}
trie = trie.search(letter);
if (trie.word != null) {
result.add(trie.word);
}
board[row][col] = '#';
for (int[] option : options) {
int r = row + option[0];
int c = col + option[1];
dfs(board, r, c, trie, result);
}
board[row][col] = letter;
}
public static class Trie {
Trie[] children = new Trie[26];
String word;
public void insert(String word) {
Trie curr = this;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (curr.children[c - 'a'] == null) {
curr.children[c - 'a'] = new Trie();
}
curr = curr.children[c - 'a'];
}
curr.word = word;
}
public boolean containsLetter(char letter) {
int idx = letter - 'a';
if (idx < 0 || idx >= children.length) {
return false;
}
return children[idx] != null;
}
public Trie search(char letter) {
return children[letter - 'a'];
}
}