剑指 Offer 12. 矩阵中的路径

解题思路：DFS

本题可以使用 DFS + 剪枝的思想解决

所谓的 DFS 是指：通过递归函数先朝着一个方向搜索到底，如果不符合题意就回溯至上一个节点，再沿着另一个方向搜索，直至找到答案。

剪枝是指：在 DFS 搜索中，我们需要标记哪些节点是已经是被访问过的，通常我的做法是使用一个数组 visited 来标记哪些节点被访问过，哪些节点没有被访问。

代码思路：

  • 当前元素在矩阵 board 中的行列索引分别为 i 和 j ；当前目标字符在 word 中的索引为 k。
  • DFS 递归返回条件：
    • 行或列索引越界，返回 false
    • 当前矩阵元素已被访问过，返回 false
    • 当前矩阵元素与目标字符不同，返回 false
    • k == len(word) - 1，也就是 word 所有字符都匹配，返回 true
  • DFS 递归过程：
    • 首先标记当前位置是访问过的：visited[i][j] = true
    • 搜索下一个路径的节点：朝当前元素的上，下，左，右 四个方向递归，找到一条可行的路径即返回
    • 还原标记过的位置 visited[i][j] = false

代码

Java

  1. class Solution {
  2.     public boolean exist(char[][] board, String word) {
  3.         int r = board.length;
  4.         int c = board[0].length;
  6.         boolean[][] visited = new boolean[r][c];
  7.         for(int i  = 0; i < r; i++){
  8.             for(int j = 0; j < c; j++){
  9.                 if(dfs(board,word,i,j,0,visited)) {
  10.                     return true;
  11.                 }
  12.             }
  13.         }
  15.         return false;
  16.     }
  18.     private static boolean dfs(char[][] board,String word,int i,int j,int k,boolean[][] visited){
  19.         if(i < 0 || i >= board.length || 
  20.            j < 0 || j >= board[0].length || 
  21.            visited[i][j] == true || 
  22.            board[i][j] != word.charAt(k)){
  23.             return false;
  24.         }
  25.         if(k == word.length() - 1){
  26.             return true;
  27.         }
  28.         visited[i][j] = true;
  30.         boolean res =
  31.             dfs(board,word,i - 1,j,k + 1,visited) ||
  32.             dfs(board,word,i + 1,j,k + 1,visited) ||
  33.             dfs(board,word,i,j - 1,k + 1,visited) ||
  34.             dfs(board,word,i,j + 1,k + 1,visited);
  35.         if(!res){
  36.             visited[i][j] = false;
  37.         }    
  39.         return res;
  40.     }
  41. }

复杂度分析

  • 时间复杂度：O(3 ^ K ) ×O(MN)
    • M 与 N 分别代表矩阵的行与列；最差的情况，我们需要遍历矩阵中长度为 K 的字符串的所有方案，也就是说搜索每个字符的上，下，左，右 四个方向，舍弃回头(上) 的方向，剩下 3 种选择，因此时间复杂度为 ：O(3 ^ K ) ×O(MN)
  • 空间复杂度：O(K) + O(MN)
    • 我们需要开辟一个 visited 数组，消耗 O(MN) 的额外空间，并且因为涉及到递归函数，所以涉及到系统调用方法栈的深度，最大深度不超过 K，所以消耗的额外空间为：O(K) + O(MN)