剑指offer 12

灰太狼 2022-11-04 01:36 44阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70]

## js ##

/** * @param {character[][]} board * @param {string} word * @return {boolean} */
    var exist = function(board, word) { 
        const row = board.length;
        const column = board[0].length;
        function dfs(arr,r,c,word,index){ 
            if(r<0||r>=row||c<0||c>column||arr[r][c]!=word[index]) return false;
            if(index == word.length-1) return true;
            let tmp = board[r][c];
            board[r][c]='-';
            let res = dfs(board,r-1,c,word,index+1)||dfs(board,r+1,c,word,index+1)||dfs(board,r,c-1,word,index+1)||dfs(board,r,c+1,word,index+1);
            board[r][c]= tmp;
            return res;
        }
       
            for(var i = 0;i < row; i++){ 
            for(var j = 0; j < column; j++){ 
                if(dfs(board,i,j,word,0)) return true;
            }
        }return false;
    };

> 刚开始做有思路，写到递归就怎么也跑不对了，放弃去看了好久的题解，恍然大悟，直言学到了！

dfs遍历中四个方向都要走，为了防止走回头路，将本次的`board[r][c]`置位`-`。当本轮结束后还要复位，因为一个单元格在dfs递归中会用到多次，并且，利用`||`来确定路径的可行性，有通路则为`true`。  
时间复杂度巨大，我想到的优化是可以先找出第一个word\[0\]然后继续找。但影响好像并不大= =、

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70]: /images/20221023/8273a6efe33d4e5eb88e3d72be015094.png

发表评论取消回复

表情：

评论列表（有 0 条评论，44人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指 Offer 12. 矩阵中的路径

后端小知识带你玩算法

矫情吗；*/ 2024年04月20日 07:23/ 0 赞/ 108 阅读

相关剑指offer：12-17记录

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的

妖狐艹你老母/ 2023年07月13日 03:02/ 0 赞/ 61 阅读

相关剑指offer | 12. 矩阵中的路径

题目内容 > 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条

矫情吗；*/ 2022年12月23日 11:27/ 0 赞/ 179 阅读

相关剑指 Offer 12. 矩阵中的路径

题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径

柔光的暖阳◎/ 2022年12月06日 15:10/ 0 赞/ 310 阅读

相关【剑指Offer】12. 矩阵中的路径

题目描述判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向上下左右移动一个格子。如果一条路径经过了矩阵中的

àì夳堔傛蜴生んèń/ 2022年11月24日 16:21/ 0 赞/ 217 阅读

相关剑指offer 12

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

灰太狼/ 2022年11月04日 01:36/ 0 赞/ 45 阅读

相关剑指offer面试题12 (二)

最近在研究<<剑指offer>>这本书，觉得这本书是必须要看的一本书，它里面讲的面试题真的很经典，下面我们就<<剑指offer>>中的面试题12：打印1到最大的n位数来看看面

谁践踏了优雅/ 2022年07月24日 06:08/ 0 赞/ 196 阅读

相关剑指offer-问题12

package offer; / offer interview 12 / public class Test12 {

怼烎@/ 2022年05月10日 14:46/ 0 赞/ 173 阅读

相关剑指Offer12:矩阵中的路径

请设计一个函数，用来判断矩阵中是否存在包含某一条字符串的所有路径，路径可以从任意一格开始，上下左右，一条路径经过矩阵某一格，不可以再次进入。在 char[][] nu

缺乏、安全感/ 2022年02月18日 16:55/ 0 赞/ 282 阅读

相关剑指offer--（12）矩形覆盖

剑指offer–（12）矩形覆盖 \ 问题描述\ 我们可以用2\1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\1的小矩形无重叠地覆盖一个2\n的大矩形，总共

短命女/ 2021年09月23日 03:48/ 0 赞/ 377 阅读