.jpg)
886 字
4 分钟
单词搜索
题目描述
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
解题思路
- 核心算法选择：采用深度优先搜索（DFS）+ 回溯算法，从网格每个位置出发尝试匹配单词。
- 起点遍历：遍历网格的每个单元格作为搜索起点，启动DFS匹配。
- 递归匹配：对于当前位置，检查是否匹配单词当前字符，然后向四个方向（上、下、左、右）递归搜索下一字符。
- 回溯机制：使用临时标记（如修改为特殊字符
#）避免重复访问，递归后恢复网格状态。 - 终止条件：
- 成功：匹配完单词所有字符
- 失败：越界/字符不匹配/重复访问
- 剪枝优化：发现有效路径立即返回，不再继续搜索。
关键洞察
- 状态回溯：通过临时修改网格标记访问状态（代替额外存储），回溯时恢复原值，空间优化至O(1)。
- 方向向量简化：用
[[0,1],[1,0],[0,-1],[-1,0]]统一处理四个方向搜索，避免冗余代码。 - 短路返回：任一方向匹配成功立即层层返回结果，避免无效搜索。
- 失败条件优先级：优先判断越界/字符不匹配（开销小），再检查重复访问。
- 起点优化：可先快速校验首字母是否存在网格中（非必须但可优化极端情况）。
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(M×N×4^L)：M×N为网格大小，L为单词长度。最坏情况需遍历所有路径（每个位置4个方向选择，递归深度L）。 |
| 空间复杂度 | O(L)：主要取决于递归栈深度（最大深度L），标记访问状态通过原地修改网格实现，无需额外存储空间。 |
注：实际性能通常远优于最坏复杂度，因剪枝策略能快速终止无效路径。
代码实现
/** * @param {character[][]} board * @param {string} word * @return {boolean} */var exist = function (board, word) { const R = board.length; const C = board[0].length;
const backTracking = (board, word, r, c, count) => { if (count === word.length) return true; let flag = word.charAt(count);
if (r < 0 || r === board.length || c < 0 || c === board[0].length || board[r][c] !== flag) return false; board[r][c] = '*';
if (backTracking(board, word, r + 1, c, count + 1) || backTracking(board, word, r - 1, c, count + 1) || backTracking(board, word, r, c + 1, count + 1) || backTracking(board, word, r, c - 1, count + 1)) return true;
board[r][c] = flag; return false; }
for (let r = 0; r < R; r++) { for (let c = 0; c < C; c++) { if (backTracking(board, word, r, c, 0)) { return true; } } } return false};实际应用场景
- 文字解谜游戏：实现Boggle等单词搜索游戏`
- 基因序列分析：DNA网格中寻找特定序列`
- 触摸屏输入：滑动输入法的单词识别`
- 网络安全：敏感词矩阵检测`
性能优化技巧
- 前缀树（Trie）：批量搜索时使用Trie提前终止无效路径`
- 频率剪枝：检查单词字符频率是否超出网格字符频率`
- 并行搜索：使用Web Worker并行处理不同起始点`
- 方向优化：根据单词长度优先选择可能方向`