【每日算法】LeetCode 79. 单词搜索

对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 79. 单词搜索

1. 题目描述

给定一个m x n的二维字符网格board和一个字符串单词word。要求找出单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：
输入：board =[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word ="ABCCED"
输出：true
解释：在网格中可以找到一条路径A->B->C->C->E->D。

示例 2：
输入：board =[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word ="SEE"
输出：true

示例 3：
输入：board =[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word ="ABCB"
输出：false

2. 问题分析

这是一个典型的二维平面上的搜索（遍历）问题，需要在有限的、有约束的空间内寻找一条特定路径。其核心特征包括：

1. 搜索空间：m x n的二维网格。
2. 约束条件：
   • 路径必须连续（上下左右四个方向）。
   • 路径不能重复使用同一个网格单元。
   • 路径的字符序列必须完全匹配目标单词。
3. 目标：判断是否存在至少一条满足条件的路径。

从前端视角看，这类问题类似于：

• 可视化搭建平台：检查用户绘制的连线图是否能形成某个特定序列。
• 游戏逻辑：如“一笔画”、“寻找单词”等小游戏的底层判断逻辑。
• DOM 树或虚拟 DOM 的特定节点序列查找：在复杂的树形结构中，寻找符合特定规则的节点路径。

3. 解题思路（给出复杂度并指出最优解）

面对此类“在约束条件下寻找所有可能路径”的问题，深度优先搜索（DFS）配合回溯是直觉且主流的解法。这也是本题的最优解，因为我们需要探索“一条路走到黑”的可能性，并在失败时“回头”尝试其他岔路。

核心思路（回溯算法）：

1. 起点：遍历网格中的每一个单元格(i, j)，将其作为搜索的起点。
2. DFS 递归搜索：从当前单元格出发，向上下左右四个方向进行递归探索。
3. 递归定义：定义函数dfs(i, j, k)，表示从网格(i, j)位置开始，能否匹配到单词word从第k个字符开始的后缀。
4. 递归三部曲：
   • 终止条件：
     • k === word.length：说明已经成功匹配整个单词，返回true。
     • i或j越界，或board[i][j] !== word[k]，或当前单元格已被访问：当前路径失败，返回false。
   • 处理当前层：标记当前单元格(i, j)为“已访问”，防止在本轮搜索中重复使用。
   • 下探到下一层：向四个方向(i+1, j),(i-1, j),(i, j+1),(i, j-1)发起递归调用dfs(nextI, nextJ, k+1)。
   • 回溯清理：这是关键步骤。在从当前单元格返回之前，撤销对其的“已访问”标记，以便其他搜索路径可以正常使用该单元格。
5. 结果整合：如果任何起点的 DFS 返回true，则最终结果为true；否则为false。

为什么这是最优解？

• 该算法本质上是穷举所有可能的路径，但由于引入了“访问标记”和及时剪枝（字符不匹配立即返回），避免了大量的无效搜索。
• 其时间复杂度在 worst-case 下虽为指数级，但对于此类 NP 难问题的子集，回溯是已知最有效的精确解法。
• 空间复杂度主要取决于递归调用栈的深度，最大为单词长度L，是可控的。

4. 各思路代码实现 (JavaScript)

4.1 思路一：DFS + 回溯（最优解实现）

/** * @param {character[][]} board * @param {string} word * @return {boolean} */varexist=function(board,word){constm=board.length;constn=board[0].length;constwordLen=word.length;// 方向数组，代表上下左右四个方向的偏移量constdirections=[[0,1],[0,-1],[1,0],[-1,0]];// 用于标记单元格是否在当前搜索路径中被访问过constvisited=newArray(m).fill(0).map(()=>newArray(n).fill(false));/** * DFS 回溯函数 * @param {number} i - 当前行索引 * @param {number} j - 当前列索引 * @param {number} k - 当前匹配到单词的第几个字符 (0-indexed) * @return {boolean} */constdfs=(i,j,k)=>{// 1. 递归终止条件（失败）if(i<0||i>=m||j<0||j>=n||visited[i][j]||board[i][j]!==word[k]){returnfalse;}// 2. 递归终止条件（成功）if(k===wordLen-1){returntrue;}// 3. 处理当前层：标记为已访问visited[i][j]=true;// 4. 递归下探到下一层（四个方向）for(const[dx,dy]ofdirections){constnewI=i+dx;constnewJ=j+dy;// 如果任意一个方向能找到剩余部分，立即返回true，不再探索其他方向if(dfs(newI,newJ,k+1)){// 注意：这里返回前也需要清理visited？不，因为成功找到了，整个调用栈会依次返回true，visited的状态不再重要。// 但为了逻辑清晰和 visited 数组的复用，可以在最终返回前统一清理，或者在成功路径返回前也清理。// 更常见的做法是：在最终成功返回true前，先清理当前节点的状态，确保函数退出时状态是干净的。// 我们调整一下代码结构，将清理放在 finally 位置。visited[i][j]=false;// 回溯，清理当前节点状态returntrue;}}// 5. 四个方向都走不通，回溯：撤销当前节点的访问标记visited[i][j]=false;returnfalse;};// 主循环：尝试每一个单元格作为起点for(leti=0;i<m;i++){for(letj=0;j<n;j++){// 优化：如果起点字符就不匹配，直接跳过if(board[i][j]===word[0]){if(dfs(i,j,0)){returntrue;}}}}returnfalse;};

优化技巧（代码中已体现）：

1. 方向数组：使代码更简洁，避免写四个类似的递归调用。
2. 起点字符预判：在调用dfs前，先判断起点字符是否匹配单词首字符，减少不必要的递归入口。
3. 回溯状态的及时清理：确保递归函数返回后，visited状态恢复到进入前的样子，这是回溯算法的精髓。

5. 各实现思路的复杂度、优缺点对比表格

6. 总结

LeetCode 79. 单词搜索是一道经典的回溯算法入门题，它清晰地展示了DFS在探索所有可能性、遇到障碍时回退的完整流程。

对前端开发者的核心价值：

1. 算法思维训练：强化“递归+回溯”的思维模式。这种模式在前端处理树形结构操作（如虚拟DOM的diff、目录树的展开/收起、权限路由的递归检查）、状态空间搜索（如表单配置的多步骤验证、工作流审批路径）时非常有用。
2. 解决实际问题：
   • 在线文档/表格：实现类似“公式追踪”功能，查找某个单元格的值是如何由其他单元格计算而来的路径。
   • 可视化搭建/低代码平台：检查用户拖拽连接的组件节点是否能形成一条有效的逻辑链。
   • 游戏开发：开发网页版的“Boggle”（找单词）或“数独”类游戏，核心逻辑就是此类网格搜索。
3. 性能意识提升：通过分析该算法的时间复杂度，你会更深刻地理解为什么某些DOM操作（如深度嵌套的递归查询）或大规模数据遍历会成为性能瓶颈，从而在设计阶段就考虑优化方案。