剑指 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 };

 

上一篇:C语言数组实现扫雷


下一篇:Leetcode No.130 被围绕的区域(DFS)