前言🌧️

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

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

当然，学习也是有侧重点的，作为前端我们不需要像后端开发一样对算法全盘掌握，有些比较偏、不实用的类型和解法，只要稍做了解即可。

题目🦀

剑指 Offer 12. 矩阵中的路径

难度中等

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

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

例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。

示例 1：

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

示例 2：

输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false

提示：

• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• board 和 word 仅由大小写英文字母组成

解题思路🌵

• 本题采用DFS,回溯算法来做
• 1、在二维字符网格中枚举每个单词的起点。
• 先从头遍历矩阵，找到第一个符合的字符，开始深度优先遍历
• 定义index代表索引，或者说已经匹配了多少个字符
• 要写递归的出口：x、y越界或者字符不匹配
• 匹配成功：index等于word.length - 1，匹配成功，直接返回true
• 为了同一个单元格内的字母不允许被重复使用，遍历到某字符后，将当前字符设置为'' "，防止四个方向dfs再次遍历到
• 四个方向遍历完毕后，再恢复这个字符
• 最后若一直匹配失败，返回false

图解 🦆

源码🔥

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
const exist = (board, word) => {
  const row = board.length
  const column = board[0].length
  const dfs = (x, y, index) => {
      //处理越界、字符不匹配的情况
      if(x<0||x>row-1||y<0||y>column-1||board[x][y]!==word[index]){return false}
      //当索引长度等于字符长度减1 就匹配成功了
      if(index===word.length-1){return true}
      //保存当前字符
        const temp = board[x][y];
        //将字符设置为空，防止四个方向dfs再次遍历到(同一个单元格内的字母不允许被重复使用)
        board[x][y]='';
    const result =
      dfs(x - 1, y, index + 1) ||
      dfs(x + 1, y, index + 1) ||
      dfs(x, y + 1, index + 1) ||
      dfs(x, y - 1, index + 1);
        //恢复当前字符
      board[x][y] = temp
      return result
  }
    for(let i=0;i<row;i++){
        for(let j=0;j<column;j++){
            if(dfs(i,j,0))return true
        } 
    }
    return false
};

时间复杂度：O(3^KMN)  MN为矩阵的宽高

空间复杂度 O(MN) ：

结束语🌞

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