Article / 文章
LeetCode 第212题：单词搜索 II
给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中"相邻"单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
题目描述
给定一个 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.lengthn == board[i].length1 <= m, n <= 12board[i][j]是一个小写英文字母1 <= words.length <= 3 * 10^41 <= words[i].length <= 10words[i]由小写英文字母组成words中的所有字符串互不相同
解题思路
这道题是经典的单词搜索问题的升级版，需要在二维字符网格中找到多个单词。如果对每个单词都独立进行DFS搜索，效率会很低。因此，我们可以利用Trie（前缀树）数据结构来优化搜索过程。
方法：Trie + DFS
解题步骤：
- 构建Trie树，将words中的所有单词插入
- 遍历二维网格board的每个单元格，以每个单元格为起点进行DFS搜索
- 在DFS搜索过程中，同时在Trie树上移动，只有当Trie中存在对应前缀时才继续搜索
- 当找到Trie树中标记为单词结尾的节点时，将对应单词加入结果集
- 为避免重复使用单元格，在DFS过程中标记已访问的单元格，回溯时恢复
关键优化点：
- 使用Trie树快速判断当前路径是否是任何单词的前缀，避免无效搜索
- 当找到单词后，在Trie中标记该单词已被找到，避免重复添加到结果集
- 可以在搜索过程中修改原网格来标记已访问，然后恢复，避免使用额外的访问标记数组
时间复杂度：O(M * N * 4^L)，其中M和N是网格的大小，L是单词的最大长度。每个单元格最多有4个方向可以搜索，路径长度最大为L。 空间复杂度：O(K)，其中K是所有单词的字符总数，用于构建Trie树。
代码实现
C# 实现
public class Solution {
private class TrieNode {
public TrieNode[] Children { get; }
public string Word { get; set; }
public TrieNode() {
Children = new TrieNode[26];
Word = null;
}
}
private TrieNode root;
private IList<string> result;
private char[][] board;
private int rows, cols;
// 四个方向：上、右、下、左
private int[] dx = {-1, 0, 1, 0};
private int[] dy = {0, 1, 0, -1};
public IList<string> FindWords(char[][] board, string[] words) {
this.board = board;
result = new List<string>();
if (board == null || board.Length == 0 || words == null || words.Length == 0) {
return result;
}
// 构建Trie树
BuildTrie(words);
rows = board.Length;
cols = board[0].Length;
// 以每个单元格为起点进行DFS
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
DFS(i, j, root);
}
}
return result;
}
private void BuildTrie(string[] words) {
root = new TrieNode();
foreach (string word in words) {
TrieNode node = root;
foreach (char c in word) {
int index = c - 'a';
if (node.Children[index] == null) {
node.Children[index] = new TrieNode();
}
node = node.Children[index];
}
node.Word = word; // 标记单词结尾并存储完整单词
}
}
private void DFS(int i, int j, TrieNode node) {
// 检查边界条件和当前单元格是否有效
if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] == '#') {
return;
}
char c = board[i][j];
int index = c - 'a';
// 当前字符不在Trie中，直接返回
if (node.Children[index] == null) {
return;
}
// 移动到Trie的下一个节点
node = node.Children[index];
// 找到了一个单词
if (node.Word != null) {
result.Add(node.Word);
node.Word = null; // 防止重复添加
}
// 标记当前单元格为已访问
board[i][j] = '#';
// 探索四个方向
for (int k = 0; k < 4; k++) {
int newI = i + dx[k];
int newJ = j + dy[k];
DFS(newI, newJ, node);
}
// 回溯，恢复单元格
board[i][j] = c;
}
}Python 实现
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
# 构建Trie树
trie = {}
for word in words:
node = trie
for char in word:
if char not in node:
node[char] = {}
node = node[char]
node['$'] = word # 使用'$'标记单词结尾并存储完整单词
rows, cols = len(board), len(board[0])
result = []
def dfs(i, j, node):
# 检查边界条件和当前单元格是否有效
if (i < 0 or i >= rows or j < 0 or j >= cols or
board[i][j] == '#' or board[i][j] not in node):
return
char = board[i][j]
curr_node = node[char]
# 找到了一个单词
if '$' in curr_node:
result.append(curr_node['$'])
curr_node.pop('$') # 防止重复添加
# 标记当前单元格为已访问
board[i][j] = '#'
# 探索四个方向
for di, dj in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
dfs(i + di, j + dj, curr_node)
# 回溯，恢复单元格
board[i][j] = char
# 优化：如果当前节点没有子节点，可以从父节点中移除（剪枝）
if not curr_node:
node.pop(char)
# 以每个单元格为起点进行DFS
for i in range(rows):
for j in range(cols):
dfs(i, j, trie)
return resultC++ 实现
class Solution {
private:
struct TrieNode {
TrieNode* children[26];
string word;
TrieNode() {
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
word = "";
}
~TrieNode() {
for (int i = 0; i < 26; i++) {
if (children[i]) {
delete children[i];
}
}
}
};
TrieNode* root;
vector<string> result;
vector<vector<char>> board;
int rows, cols;
// 四个方向：上、右、下、左
vector<int> dx = {-1, 0, 1, 0};
vector<int> dy = {0, 1, 0, -1};
void buildTrie(vector<string>& words) {
root = new TrieNode();
for (const string& word : words) {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (!node->children[index]) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->word = word; // 标记单词结尾并存储完整单词
}
}
void dfs(int i, int j, TrieNode* node) {
// 检查边界条件和当前单元格是否有效
if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] == '#') {
return;
}
char c = board[i][j];
int index = c - 'a';
// 当前字符不在Trie中，直接返回
if (!node->children[index]) {
return;
}
// 移动到Trie的下一个节点
node = node->children[index];
// 找到了一个单词
if (!node->word.empty()) {
result.push_back(node->word);
node->word = ""; // 防止重复添加
}
// 标记当前单元格为已访问
board[i][j] = '#';
// 探索四个方向
for (int k = 0; k < 4; k++) {
int newI = i + dx[k];
int newJ = j + dy[k];
dfs(newI, newJ, node);
}
// 回溯，恢复单元格
board[i][j] = c;
}
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
this->board = board;
result.clear();
if (board.empty() || board[0].empty() || words.empty()) {
return result;
}
// 构建Trie树
buildTrie(words);
rows = board.size();
cols = board[0].size();
// 以每个单元格为起点进行DFS
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
dfs(i, j, root);
}
}
return result;
}
~Solution() {
delete root;
}
};性能分析
各语言实现的性能对比：
| 实现语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 500 ms | 45.2 MB | 基本Trie+DFS实现 |
| Python | 256 ms | 33.8 MB | 使用字典实现Trie，动态剪枝 |
| C++ | 160 ms | 12.5 MB | 最佳性能，高效内存管理 |
补充说明
代码亮点
- 使用Trie树优化单词查找，避免重复搜索相同前缀
- DFS与Trie树结合，在图和树中同时进行搜索
- 通过修改网格值标记访问状态，避免使用额外的访问数组
- Python实现中的剪枝操作：移除没有子节点的Trie节点，进一步提高效率
优化策略
- 前缀树优化：使用Trie树减少不必要的搜索路径
- 原地标记：使用特殊字符（如’#’）标记已访问单元格，避免额外空间
- 剪枝优化：Python实现中，当Trie节点没有子节点时，从父节点中删除，进一步提高效率
- 查找去重：找到单词后清除Trie节点中的标记，避免重复添加到结果集
解题难点
- 如何高效表示和搜索大量单词：使用Trie树减少搜索空间
- 如何处理单元格不能重复使用：DFS中标记已访问单元格，回溯时恢复
- 如何避免结果中的重复单词：在Trie中清除已找到的单词标记
常见错误
- 没有正确处理网格边界条件
- 忘记在回溯时恢复单元格状态
- 没有防止重复添加同一单词到结果集
- Trie树实现错误，无法正确匹配单词