前言🌧️
算法,对前端人来说陌生又熟悉,很多时候我们都不会像后端工程师一样重视这项能力。但事实上,算法对每一个程序员来说,都有着不可撼动的地位。
因为开发的过程就是把实际问题转换成计算机可识别的指令,也就是《数据结构》里说的,「设计出数据结构,在施加以算法就行了」。
编写指令的好坏,会直接影响到程序的性能优劣,而指令又由数据结构和算法组成,所以数据结构和算法的设计基本上决定了最终程序的好坏。
题目🦀
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.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board
和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-单词搜索⚡️
就结束了,算法这个东西没有捷径,只能多写多练,多总结,文章的目的其实很简单,就是督促自己去完成算法练习并总结和输出,菜不菜不重要,但是热爱🔥,喜欢大家能够喜欢我的短文,也希望通过文章认识更多志同道合的朋友,如果你也喜欢折腾
,欢迎加我好友
,一起沙雕
,一起进步
。