「LeetCode」79-单词搜索⚡️

简介: 「LeetCode」79-单词搜索⚡️

image.png

前言🌧️


算法,对前端人来说陌生又熟悉,很多时候我们都不会像后端工程师一样重视这项能力。但事实上,算法对每一个程序员来说,都有着不可撼动的地位。


因为开发的过程就是把实际问题转换成计算机可识别的指令,也就是《数据结构》里说的,「设计出数据结构,在施加以算法就行了」。


编写指令的好坏,会直接影响到程序的性能优劣,而指令又由数据结构和算法组成,所以数据结构和算法的设计基本上决定了最终程序的好坏


题目🦀



79. 单词搜索


难度中等


给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false


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


示例 1:

image.png

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true


示例 2


image.png


输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出:true


示例 3:


image.png


输入: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
  • boardword 仅由大小写英文字母组成


**进阶:**你可以使用搜索剪枝的技术来优化解决方案,使其在 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)


结束语🌞


image.png

那么鱼鱼的LeetCode算法篇的「LeetCode」79-单词搜索⚡️就结束了,算法这个东西没有捷径,只能多写多练,多总结,文章的目的其实很简单,就是督促自己去完成算法练习并总结和输出,菜不菜不重要,但是热爱🔥,喜欢大家能够喜欢我的短文,也希望通过文章认识更多志同道合的朋友,如果你也喜欢折腾,欢迎加我好友,一起沙雕,一起进步

相关文章
|
27天前
|
算法 索引
LeetCode(搜索插入位置)
如何使用二分查找算法来解决LeetCode上的“搜索插入位置”问题,确保时间复杂度为O(log n),并提供了详细的代码实现和分析。
14 2
|
27天前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
16 0
Leetcode第三十三题(搜索旋转排序数组)
|
26天前
【LeetCode 39】700.二叉搜索树中的搜索
【LeetCode 39】700.二叉搜索树中的搜索
12 0
|
27天前
Leetcode(最后一个单词长度)
这篇文章介绍了两种解决LeetCode第58题的方法,即计算给定字符串中最后一个单词的长度,方法包括翻转字符串和逆向遍历统计。
15 0
|
27天前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
17 0
|
3月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
3月前
|
算法
LeetCode第74题搜索二维矩阵
文章讲解了LeetCode第74题"搜索二维矩阵"的解决方案,利用二分搜索法将问题简化,并通过数学转换找到二维矩阵中的对应元素,展示了将二维问题转化为一维问题的解题技巧。
LeetCode第74题搜索二维矩阵
|
3月前
|
算法
LeetCode第58题最后一个单词的长度
LeetCode第58题"最后一个单词的长度"的解题方法,通过从字符串末尾向前遍历并计数非空格字符,直接得出最后一个单词的长度。
LeetCode第58题最后一个单词的长度
|
3月前
|
算法
LeetCode第35题搜索插入位置
这篇文章介绍了LeetCode第35题"搜索插入位置"的解题方法,通过使用二分查找法,高效地找到在有序数组中插入一个目标数的最佳位置。
LeetCode第35题搜索插入位置
|
3月前
|
算法
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组