前言🌧️
算法，对前端人来说陌生又熟悉，很多时候我们都不会像后端工程师一样重视这项能力。但事实上，算法对每一个程序员来说，都有着不可撼动的地位。
因为开发的过程就是把实际问题转换成计算机可识别的指令，也就是《数据结构》里说的，「设计出数据结构，在施加以算法就行了」。
编写指令的好坏，会直接影响到程序的性能优劣，而指令又由数据结构和算法组成，所以数据结构和算法的设计基本上决定了最终程序的好坏。
题目🦀
79. 单词搜索
难度中等
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true
示例 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
提示：
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board和word仅由大小写英文字母组成
**进阶：**你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
解题思路🌵
- 使用回溯算法来解决此类搜索路经的问题
- 注意边界条件和记录当前记录过的值
- 从题目的意思可以知道，其实我们是可以从矩阵的任一一个索引位置开始去查找单词的
- 使用深度优先搜索的思路，从某一个位置匹配上了单词，就继续对这个位置上下左右去匹配字符串的下一个字符 如果没有匹配上，就尽快返回false减少无用的递归处理，然后回溯
解题步骤🐂
- 先计算borad的边界
- 然后开始对矩阵的每一个索引位置开始查找单词
- 分别对上下左右的位置进行查找
- 在查找过程中遇到索引和word索引不对应的就立即返回false，超出边界的同样返回false
- 当前字符和word 索引位置对应时，记得将该值设置为false，避免接下来的查找重复搜索
- 遍历完上下左右后，记得将刚开始设置的值为false的设置回来
源码🔥
/** * @param {character[][]} board * @param {string} word * @return {boolean} */ var exist = function(board, word) { // 输入的终止条件 if(board.length===0) { return false } if(word.length===0){ return true } const [row,col]=[board.length,board[0].length] for(let i=0;i<row;i++){ for(let j=0;j<col;j++){ const result = find(i,j,0) if(result){ return result } } } function find(i,j,index){ if(i>=row||i<0){ return false } if(j>=col||j<0){ return false } if(board[i][j]!==word[index]){ return false } if(index===word.length-1){ return true } let letter=board[i][j] board[i][j]=false const result = find(i,j-1,index+1)|| find(i,j+1,index+1)|| find(i+1,j,index+1)|| find(i-1,j,index+1) board[i][j]=letter return result } return false };
时间复杂度:O(mn)
空间复杂度:O(mn)
结束语🌞
那么鱼鱼的LeetCode算法篇的「LeetCode」79-单词搜索⚡️就结束了，算法这个东西没有捷径，只能多写多练，多总结，文章的目的其实很简单，就是督促自己去完成算法练习并总结和输出，菜不菜不重要，但是热爱🔥，喜欢大家能够喜欢我的短文，也希望通过文章认识更多志同道合的朋友，如果你也喜欢折腾，欢迎加我好友，一起沙雕，一起进步。
