剑指 Offer 12. 矩阵中的路径

题目地址(12. 矩阵中的路径)

https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/

题目描述

给定一个 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 仅由大小写英文字母组成
注意：本题与主站 79 题相同：https://leetcode-cn.com/problems/word-search/

前置知识

公司

• 暂无

思路

本问题是典型的矩阵搜索问题，可使用 深度优先搜索（DFS）+ 剪枝 解决。

• 深度优先搜索： 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
• 剪枝： 在搜索中，遇到 这条路不可能和目标字符串匹配成功 的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为 可行性剪枝 。

递归参数： 当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k 。
终止条件：

• 返回 falsefalse ： (1) 行或列索引越界 或 (2) 当前矩阵元素与目标字符不同 或 (3) 当前矩阵元素已访问过 （ (3) 可合并至 (2) ） 。
• 返回 truetrue ： k = len(word) - 1 ，即字符串 word 已全部匹配。

递推工作：

• 标记当前矩阵元素： 将 board[i][j] 修改为 空字符 ‘’ ，代表此元素已访问过，防止之后搜索时重复访问。
• 搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，使用 或 连接 （代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。
• 还原当前矩阵元素： 将 board[i][j] 元素还原至初始值，即 word[k] 。

图一

图2

假设绿色的是最终要找的单词 这样e就还可以取到了

关键点

代码

• 语言支持：Java

Java Code:

class Solution {
        public boolean exist(char[][] board, String word) {
            //将单词拆解为字符数组
            char[] words = word.toCharArray();
            //遍历矩阵的每一个位置
            for (int i = 0; i < board.length ; i++) {
                for (int j = 0; j < board[0].length ; j++) {
                    //如果有一个返回了true就直接返回即可
                    if (dfs(board, i, j, words , 0)) {
                        return true;
                    }
                }
            }
            //如果到了最后都没找到 就返回false
            return false;
        }
        boolean dfs(char[][] board,int i , int j , char[] words ,int index){
            //如果ij超过了数组的边界 或者 矩阵当前下标的位置的字符!=单词的当前位置的字符 说明当前查找不到了 返回false
            if (i < 0 || j < 0 || i >= board.length || j>= board[0].length || board[i][j] != words[index]) {
                return false;
            }
            //注意顺序 这个不能放在上面 不然只有一个字符的话就会返回true了 如果index遍历到words的最后一个字符了说明找到 返回true
            if (index  == words.length -1) {
                return true;
            }
            //到这个位置说明前面的字符都对上了 继续递归当前字符的上线左右
            //将当前的字符 变成空 这样board[i][j] != words[index]判断的时候就不会再找到之前找过的字符了
            //比如 cec c遍历完该e了这时候下一个还是c 这时候e可能会再判断之前的c 这时给之前遍历过的值赋上一个不可能取到的值
            board[i][j] = '\0';
            //遍历上下左右 只要有一个返回true res就返回true
            boolean res = dfs(board, i - 1, j, words, index + 1) ||
                    dfs(board, i + 1, j, words, index + 1) ||
                    dfs(board, i, j - 1, words, index + 1) ||
                    dfs(board, i, j + 1, words, index + 1) ;
            //回溯 如果有一边走不通的话 就回溯把之前的值再还原 方便别的遍历顺序再取到这个值 见图2
            board[i][j] = words[index];
            return res;
        }
    }

复杂度分析

令 n 为数组长度。

• 时间复杂度：#card=math&code=O%28n%29&id=kPlmq)
• 空间复杂度：#card=math&code=O%28n%29&id=bA9T9)