剑指 Offer 12. 矩阵中的路径

本文主要是介绍剑指 Offer 12. 矩阵中的路径，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

方法一：dfs

首先，一定是需要遍历到矩阵中的每个元素，以其为开始再进行搜索；进入搜索后，要确定返回条件：①若超过边界则返回；②若不符合word则返回；③若以遍历过则返回；最后通过递归深度优先搜索矩阵的节点。

其中通过删除已遍历且符合要求的矩阵中的值来保证其不会重复搜索，因为已经符合要求，所以当前矩阵中的值是与word相同的，删除其值接着进行遍历，遍历结束后再将矩阵重新赋值即可。

 1 /**
 2  * @param {character[][]} board
 3  * @param {string} word
 4  * @return {boolean}
 5  */
 6 var exist = function(board, word) {
 7     let words = word.split("");
 8     let dfs = (i,j, k) => {
 9         if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != words[k]) {
10             return false;
11         }
12         if(k == words.length - 1) return true;
13         board[i][j] = "";
14         const res = dfs(i - 1, j, k + 1) ||
15                     dfs(i, j + 1, k + 1) ||
16                     dfs(i + 1, j, k + 1) ||
17                     dfs(i, j - 1, k + 1);
18         board[i][j] = words[k];
19         return res;
20     }
21     for(let i = 0; i < board.length; i++) {
22         for(let j = 0; j < board[0].length; j++) {
23             if(dfs(i, j, 0)) {
24                 return true;
25             }
26         }
27     }
28     return false;
29 };

这篇关于剑指 Offer 12. 矩阵中的路径的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！