LeetCode 212. 单词搜索 II
题目描述
题意分析
找出词典中能够由网格路径组成的所有单词。路径每次只能走到上下左右的相邻格子，同一次拼词不能重复使用格子，但不同路径可以使用同一个格子。同一个单词只需要返回一次。
如果对每个单词单独搜索，公共前缀对应的网格路径会被反复探索。可以先用 Trie 合并词典中的公共前缀，让一次网格搜索同时匹配所有仍有可能的单词。
解法：Trie 前缀树 + 回溯搜索
核心思路
[!blue]
Trie 的每条边代表一个字母，从根到某个节点的路径代表一个词前缀。终止节点的
word保存完整单词，childCount记录当前仍存在的孩子数。插入时只有真正新建孩子才增加计数，共享已有前缀不重复计数。从每个网格格子出发回溯。调用
dfs(row, col, parent)时，parent表示尚未加入当前格子之前的前缀。读取当前字符ch后，沿parent.children[ch - 'a']走到node，网格路径和 Trie 前缀便同步增加一个字符。若这个孩子不存在，说明没有尚待查找的单词以当前路径为前缀，可以立即停止，不必继续枚举后面的格子。如果
node.word非空，就找到了一个完整单词，将它加入答案并清空word。清空只用于全局去重，不恢复；但搜索不能就此结束，因为当前单词也可能是更长单词的前缀，仍需继续检查孩子。继续搜索前，把当前格子临时改为
#，防止本条路径再次使用它。然后向四个方向递归，且传入已经前进后的node。四个方向都处理完后恢复原字符，使其他路径仍可使用这个格子。网格标记是路径内的临时状态，与 Trie 中找到单词后的永久去重不同。回溯返回前，若
node.word已空且node.childCount == 0，说明该前缀下已没有未找到的单词，可以从父节点永久删除它，并将父节点孩子数减一。删除会逐层向上清理耗尽的分支。某条网格路径走不通并不能证明这个条件，不能据此删除尚未找到的单词。每个合法单词都对应一个起点和一条不重复用格子的四邻路径。只要它尚未找到，各级前缀就仍保留在 Trie 中，沿这条路径搜索便不会被提前剪掉。因此不会漏掉答案；每个终止标记又只消耗一次，所以结果也不会重复。
解题步骤
- 把所有单词插入 Trie，在终止节点存入完整单词，并维护每个节点的实际孩子数。
- 枚举网格中的每个格子作为起点，从 Trie 根节点开始调用 DFS。
- 先排除越界和已经标记的格子，再沿当前字符查找 Trie 孩子；不存在就返回。
- 若当前节点保存了单词，加入答案并清空终止标记；随后标记当前格子，向四邻递归查找更长的候选词。
- 返回时先恢复当前格子的字符，再判断 Trie 节点是否已经耗尽；只有没有终止词也没有孩子时，才删除父节点对应的边。
- 全部起点处理完后返回答案，此时网格已恢复原状。
代码实现
class Solution {
private static final int[][] DIRECTIONS = {
{1, 0},
{-1, 0},
{0, 1},
{0, -1},
};
public List<String> findWords(char[][] board, String[] words) {
TrieNode root = new TrieNode();
for (String word : words) {
insert(root, word);
}
List<String> res = new ArrayList<>();
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board[0].length; col++) {
dfs(board, row, col, root, res);
}
}
return res;
}
// 网格的当前路径与父节点的词前缀同步前进，标记只对本路径有效。
private void dfs(char[][] board, int row, int col, TrieNode parent, List<String> res) {
if (row < 0
|| row >= board.length
|| col < 0
|| col >= board[0].length
|| board[row][col] == '#') {
return;
}
char ch = board[row][col];
TrieNode node = parent.children[ch - 'a'];
if (node == null) {
return;
}
// 命中只消耗当前完整词，不能停止搜索共享该前缀的更长词。
if (node.word != null) {
res.add(node.word);
node.word = null;
}
board[row][col] = '#';
for (int[] direction : DIRECTIONS) {
dfs(board, row + direction[0], col + direction[1], node, res);
}
// 搜索结束恢复字符，其他起点与兄弟路径仍可使用这一格。
board[row][col] = ch;
// 该前缀下的单词已全部找到，后续不再搜索这条分支。
if (node.word == null && node.childCount == 0) {
parent.children[ch - 'a'] = null;
parent.childCount--;
}
}
private void insert(TrieNode root, String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
int idx = word.charAt(i) - 'a';
// 只有新建一条边才增加孩子数，公共前缀不能重复计数。
if (node.children[idx] == null) {
node.children[idx] = new TrieNode();
node.childCount++;
}
node = node.children[idx];
}
node.word = word;
}
private static class TrieNode {
private final TrieNode[] children = new TrieNode[26];
private int childCount;
private String word;
}
}
type TrieNode struct {
children [26]*TrieNode
childCount int
word string
}
func findWords(board [][]byte, words []string) []string {
root := &TrieNode{}
for _, word := range words {
insertWord(root, word)
}
res := make([]string, 0)
directions := [][2]int{
{1, 0},
{-1, 0},
{0, 1},
{0, -1},
}
var dfs func(row int, col int, parent *TrieNode)
// 网格的当前路径与父节点的词前缀同步前进，标记只对本路径有效。
dfs = func(row int, col int, parent *TrieNode) {
if row < 0 || row >= len(board) || col < 0 || col >= len(board[0]) || board[row][col] == '#' {
return
}
ch := board[row][col]
node := parent.children[ch-'a']
if node == nil {
return
}
// 命中只消耗当前完整词，不能停止搜索共享该前缀的更长词。
if node.word != "" {
res = append(res, node.word)
node.word = ""
}
board[row][col] = '#'
for _, direction := range directions {
dfs(row+direction[0], col+direction[1], node)
}
// 搜索结束恢复字符，其他起点与兄弟路径仍可使用这一格。
board[row][col] = ch
// 该前缀下的单词已全部找到，后续不再搜索这条分支。
if node.word == "" && node.childCount == 0 {
parent.children[ch-'a'] = nil
parent.childCount--
}
}
for row := 0; row < len(board); row++ {
for col := 0; col < len(board[0]); col++ {
dfs(row, col, root)
}
}
return res
}
func insertWord(root *TrieNode, word string) {
node := root
for i := 0; i < len(word); i++ {
idx := word[i] - 'a'
// 只有新建一条边才增加孩子数，公共前缀不能重复计数。
if node.children[idx] == nil {
node.children[idx] = &TrieNode{}
node.childCount++
}
node = node.children[idx]
}
node.word = word
}
复杂度分析
设网格为
m×n，词典总字符数为S，最长单词长度为L。
- 时间复杂度：$O(S + mn \cdot 4 \cdot 3^{L-1})$。建 Trie 为 $O(S)$；每个格子都可以成为起点，路径的第一步最多向四个方向扩展，此后不能走回上一格，每层最多三个方向，匹配长度不超过
L。这是忽略前缀剪枝和其他已访问格子限制的上界，删除已耗尽分支还会减少实际搜索量。- 空间复杂度：$O(S+L)$。Trie 至多创建
S个节点，递归栈深度受最长单词长度限制；网格原地标记并恢复，不需要额外访问数组。返回结果不计入辅助空间。
关键点总结
[!green]
- Trie 共享词典前缀，每走一个网格格子，也沿 Trie 前进一步。
- 网格访问标记只对当前路径有效，回溯必须恢复；找到单词后的终止标记清空则永久生效。
- 找到短词后仍要继续探索，短词的终止节点可能还有更长单词的分支。
- 只有前缀下的单词已经全部找到，才能永久删除这个分支；
childCount用于直接判断是否还有孩子。
易错点总结
[!yellow]
- 找到单词就返回：会漏掉共享这个前缀的更长单词。
- 找到后保留
word：同一个单词可能由多条路径组成，必须清空终止标记，避免重复输出。- 标记格子后没有恢复：会让其他起点或兄弟路径无法再次使用这个格子。
- 读取字符后才判断越界：四方向递归会产生越界坐标，必须先检查坐标，再检查标记和 Trie 孩子。
- 递归仍传
parent：Trie 前缀没有随着网格路径前进，下一字符会在错误的层级查找；应传入node。- 某次搜索失败就删除 Trie 分支：其他路径仍可能找到这些单词，只能删除终止词为空且无孩子的节点。
- 共享前缀也增加
childCount：计数表示实际孩子数，只有新建一条边时加一、删除一条边时减一。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 79. 单词搜索 | 中等 | 从查找单个单词扩展为查找词表，Trie合并公共前缀，减少重复网格探索。 |
| 面试题 17.17. 多次搜索 | 中等 | 同样用Trie匹配多个模式，原题在一维文本连续向右，本题在网格四方向回溯。 |
| 208. 实现 Trie (前缀树) | 中等 | 用字典树共享字符串前缀；本题把字典树与网格回溯结合，该题支持插入、完整词查询和前缀查询。 |
| 211. 添加与搜索单词 - 数据结构设计 | 中等 | 用字典树共享字符串前缀；本题把字典树与网格回溯结合，该题通配符查询时分支搜索。 |
| 648. 单词替换 | 中等 | 用字典树共享字符串前缀；本题把字典树与网格回溯结合，该题沿词前缀找到最短词根。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！