开发者社区> 答案命运> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

剑指Offer——矩阵中的路径(JS实现)

简介: 剑指Offer——矩阵中的路径(JS实现)
+关注继续查看

题目描述

image.png

image.png

解题思路

  • 本题采用的DFS + 剪枝
  • 首先通过循环遍历二维数组,找到第一个和字符串的元素相同的元素,然后使用DFS开始遍历,知道遍历到字符串的最后一个元素都相同,则返回true,反之则返回false
  • 剪枝的作用在于在进行DFS遍历的时候,防止重复遍历

解题代码

var exist = function(board, word) {
    // ! 本题采用深度优先搜索DFS的算法思想
    // 记录二维数组的行数
    const row = board.length;
    // 记录二维数组的列数
    const col = board[0].length;
    // 定义核心DFS函数
    function dfs(i,j,board,index) {
        // 如果下标越界或者元素不匹配则返回false
        if (i < 0 || i >= row || j < 0 || j >= col || board[i][j] !== word[index]) return false;
        // 经过上面的if语句,如果index走到最后一个下标,说明包含这个字符串,返回true
        if (index === word.length - 1) return true;
        // 因为前面的是起点,我们还要遍历起点之后的元素,先记录下当前元素
        let temp = board[i][j];
        // 让当前元素这个位置不能被重复参与
        board[i][j] = '*';
        // 定义一个元素的上下左右是否符合
        let res = dfs(i-1,j,board,index+1) || dfs(i+1,j,board,index + 1) || dfs(i,j-1,board,index+1) || dfs(i,j+1,board,index+1);
        // 恢复元素的原本值,让后续的遍历可以使用
        board[i][j] = temp;
        // 返回res
        return res;
    }
    // 从board中寻找第一个和word[0]相同的元素,开始遍历
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            // 只要能遍历到一个true,则返回true
            if (dfs(i,j,board,0)) return true;
        }
    }
    // 如果遍历完,都没有true,说明没有,则返回false
    return false;
};

总结(本题给我们的启示思路)

  • 启示一:学会使用DFS + 剪枝的方法遍历二维数组中的有关路径

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
基于H5+css+JavaScript实现动态线性渐变背景
基于H5+css+JavaScript实现动态线性渐变背景
25 0
基于H5+css+JavaScript实现全屏覆盖导航栏
基于H5+css+JavaScript实现全屏覆盖导航栏
43 0
css3结合JavaScript实现翻页幻灯片效果
CSS3+JavaScript实现翻页幻灯片效果
10 0
JavaScript实现简单区块链
用JavaScript来实现一个简单的区块链。通过实现过程,你将理解区块链是什么:区块链就是一个分布式数据库,存储结构是一个不断增长的链表,链表中包含着许多有序的记录。
1077 0
使用JavaScript实现一个俄罗斯方块
清明假期期间,闲的无聊,就做了一个小游戏玩玩,目前游戏逻辑上暂未发现bug,只不过样子稍微丑了一些-.-项目地址:https://github.com/Jiasm/tetris在线Demo:http://blog.
1435 0
JavaScript进阶【五】利用JavaScript实现动画的基本思路
版权声明:本文为博主原创文章,未经博主允许不得转载。更多学习资料请访问我爱科技论坛:www.52tech.tech https://blog.csdn.net/m0_37981569/article/details/79659313 ...
917 0
Javascript实现完美继承
javascipt 实现javascript完美继承要考虑三个方面: 第一步: 获取父构造函数体内的属性 解决方法: 通过 Father.
896 0
javascript oo实现
很久很久以前,我还是个phper,第一次接触javascript觉得好神奇。跟传统的oo类概念差别很大。记得刚毕业面试,如何在javascript里面实现class一直是很热门的面试题,当前面试百度就被问到了,当年作为一个小白只是网上随便搜搜应付了下。
615 0
JavaScript实现排序算法
排序算法主要用在元素的数组排序,常见的排序算法有冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序等。这些排序算法都可以用JavaScript实现。
639 0
+关注
答案命运
人有多自律,就有多自由!
文章
问答
文章排行榜
最热
最新
相关电子书
更多
Python第五讲——关于爬虫如何做js逆向的思路
立即下载
编程语言如何演化—— 以 JS 的 private 为例
立即下载
JS零基础入门教程(上册)
立即下载