0212. 单词搜索 II【困难】
1. 📝 题目描述
给定一个 m x n 二维字符网格 board 和一个单词(字符串)列表 words,返回所有二维网格上的单词。
单词必须按照字母顺序,通过 相邻的单元格 内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例 1:

txt
输入:board = [
["o","a","a","n"],
["e","t","a","e"],
["i","h","k","r"],
["i","f","l","v"]
], words = ["oath","pea","eat","rain"]
输出:["eat","oath"]1
2
3
4
5
6
7
2
3
4
5
6
7
示例 2:

txt
输入:board = [
["a","b"],
["c","d"]
], words = ["abcb"]
输出:[]1
2
3
4
5
2
3
4
5
提示:
m == board.lengthn == board[i].length1 <= m, n <= 12board[i][j]是一个小写英文字母1 <= words.length <= 3 * 10^41 <= words[i].length <= 10words[i]由小写英文字母组成words中的所有字符串互不相同
2. 🎯 s.1 - 字典树 + 回溯
c
typedef struct TrieNode {
struct TrieNode* children[26];
char* word;
} TrieNode;
TrieNode* createNode() {
return (TrieNode*)calloc(1, sizeof(TrieNode));
}
void insertWord(TrieNode* root, char* word) {
TrieNode* node = root;
for (int i = 0; word[i]; i++) {
int idx = word[i] - 'a';
if (!node->children[idx]) node->children[idx] = createNode();
node = node->children[idx];
}
node->word = word;
}
void dfs(char** board, int m, int n, int i, int j, TrieNode* node, char** res, int* resSize) {
if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] == '#') return;
int idx = board[i][j] - 'a';
if (!node->children[idx]) return;
node = node->children[idx];
if (node->word) {
res[(*resSize)++] = node->word;
node->word = NULL;
}
char tmp = board[i][j];
board[i][j] = '#';
dfs(board, m, n, i + 1, j, node, res, resSize);
dfs(board, m, n, i - 1, j, node, res, resSize);
dfs(board, m, n, i, j + 1, node, res, resSize);
dfs(board, m, n, i, j - 1, node, res, resSize);
board[i][j] = tmp;
}
char** findWords(char** board, int boardSize, int* boardColSize, char** words, int wordsSize, int* returnSize) {
TrieNode* root = createNode();
for (int i = 0; i < wordsSize; i++) insertWord(root, words[i]);
char** res = (char**)malloc(sizeof(char*) * wordsSize);
*returnSize = 0;
int m = boardSize, n = boardColSize[0];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
dfs(board, m, n, i, j, root, res, returnSize);
return res;
}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
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
js
/**
* @param {character[][]} board
* @param {string[]} words
* @return {string[]}
*/
var findWords = function (board, words) {
const root = {}
// 构建字典树
for (const word of words) {
let node = root
for (const ch of word) {
if (!node[ch]) node[ch] = {}
node = node[ch]
}
node.word = word
}
const m = board.length,
n = board[0].length
const res = []
function dfs(i, j, node) {
if (i < 0 || i >= m || j < 0 || j >= n) return
const ch = board[i][j]
if (ch === '#' || !node[ch]) return
node = node[ch]
if (node.word) {
res.push(node.word)
node.word = null // 去重
}
board[i][j] = '#'
dfs(i + 1, j, node)
dfs(i - 1, j, node)
dfs(i, j + 1, node)
dfs(i, j - 1, node)
board[i][j] = ch
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
dfs(i, j, root)
}
}
return res
}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
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
py
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = {}
for word in words:
node = root
for ch in word:
node = node.setdefault(ch, {})
node['#'] = word
m, n = len(board), len(board[0])
res = []
def dfs(i, j, node):
if i < 0 or i >= m or j < 0 or j >= n:
return
ch = board[i][j]
if ch not in node:
return
node = node[ch]
if '#' in node:
res.append(node.pop('#'))
board[i][j] = '.'
dfs(i + 1, j, node)
dfs(i - 1, j, node)
dfs(i, j + 1, node)
dfs(i, j - 1, node)
board[i][j] = ch
for i in range(m):
for j in range(n):
dfs(i, j, root)
return res1
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
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
- 时间复杂度:
,其中 是网格大小, 是单词最大长度 - 空间复杂度:
,其中 是所有单词的字符总数
算法思路:
- 将所有单词插入字典树,然后从网格每个位置出发 DFS
- 沿着字典树节点探索,节点不存在则剪枝,找到单词后置空以去重