剑指Offer 面试题 12：矩阵中的路径（DFS做法，超详解）

水深无声 2023-02-14 15:45 51阅读 0赞

题目：

> 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的**任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格**。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。

> 例如，在下面的 3×4 的矩阵中包含一条字符串 “bfce” 的路径（路径中的字母用加粗标出）。

> \[\[“a”,“b”,“c”,“e”\],  
> \[“s”,“f”,“c”,“s”\],  
> \[“a”,“d”,“e”,“e”\]\]

> 但矩阵中不包含字符串 “abfb” 的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

示例 1：  
输入：board = \[\[“A”,“B”,“C”,“E”\],\[“S”,“F”,“C”,“S”\],\[“A”,“D”,“E”,“E”\]\], word = “ABCCED”  
输出：true  
![在这里插入图片描述][20200603162933781.png]  
示例 2：  
输入：board = \[\[“a”,“b”\],\[“c”,“d”\]\], word = “abcd”  
输出：false  
![在这里插入图片描述][20200603163001357.png]  
提示：  
1 <= board.length <= 200  
1 <= board\[i\].length <= 200

题目和示例到这里就结束了，现在我们来分析题目。

### 一、DFS ###

#### 1.1 ####

几个注意事项：

*  根据最终结果来看，这个题目中 “ **包含某字符串所有字符** ” 的意思是，严格相等。也就是说，找 abb ，那么你找到 adbb 这样的 “ 包含 ” 是不算数的。
 *  这个深度优先搜索问题，搜索的**开始位置**是不确定的，可能在 board 这个二维数组的任意一个位置。  
    对于待匹配的字符串 word 的第一个字符，可能 board 里面多个位置都是 word 的第一个字符，而从这多个位置开始的搜索结果 并不相同，因此要遍历整个二维数组，从每一个位置都进行深度优先搜索。

目前为止，整个过程了解了，就是一个 **搜索+返回结果** 的问题。我们用代码来表示，也就是：

for(int i = 0; i < board.length; i++) {
        
           for(int j = 0; j < board[0].length; j++) {
        
               //从任何一个位置开始搜索，找到满足条件的路径即可直接返回。
               if(dfs(board, words, i, j, 0)){
        
                   return true;
               }
           }
       }

#### 1.2 ####

那么接下来，我们要思考的就是 **dfs 的过程**，即 dfs() 这个方体怎么实现。

对于整体代码框架里，每一个遍历到的元素 **board\[i\]\[j\]** ，需要做三件事：

1.  **判断这个元素是否满足要求**，这决定了我们要沿这条路继续进行深度优先搜索，还是退回到上一步。  
    判断当前位置是否越界，判断这个位置的值和搜索的字符是否匹配，  
    如果答案是 true ，继续第二步，如果不是，那只能退回去一步。
2.  **在第一步满足的条件下，继续向四周进行搜索**。  
    四周的元素都可能作为下一步的路径，所以分别对他们调用这个递归的方法。
3.  **是不是到了结束条件**。  
    正常结束条件，也就是待匹配的 word 到了最后一个元素，这代表，所有word 的字符都被搜索到了，就可以return true，  
    非正常结束条件，因为路到底了而返回，或者这个位置的值和搜索的字符不匹配，也要返回，这里就用到了题目约束的，严格包含，也就是当前字符不匹配了，沿着他没有必要继续下去。。要直接return false（和 1 的条件有重复，合并）。

**对于 1 这一步来说**，还应该包括，**当前遍历到的位置是不是已经被标记为走过了**的判断（由于路径不能重复）  
怎么标记呢？答案是：只有在某一个位置满足条件，被划进了搜索路径里的时候才需要标记，其他情况都不用。

> （开始我认为，这个元素不匹配，那之后的路都堵死了，都不用走了，岂不是也需要标记？  
> 但是再想想，如果因为这样而标记，那会错过**其他拐弯到达这里**的路径，会影响结果的正确性。）

**对于2 这一步来说**，也需要对应的，进行 “标记” 的操作，如果满足条件，在继续想四周搜索之前，要把当前位置标记为已经访问。

> 直接标记了就完事了吗？  
> 这一步如果进行了标记，那么一样会影响到**其他拐弯到达这里**的路径，因此我们只能让**采用当前这一种搜索方案 带着这个标记进行下去。**

#### 1.3 ####

现在，已经有了 dfs 方法里需要做的事，我们来设计 dfs 函数需要的参数：

*  矩阵本身
 *  对应二维的坐标 i 和 j
 *  待匹配的字符串
 *  待匹配字符串的下标（由于要一个一个字符进行对照）

写出代码：

boolean dfs( char[][] board, int i,int j, char[] word, int k )

#### 1.4 ####

最后我们就可以写出方法体里各部分的代码实现：

**1.4.1对应到第一步**，判断是否满足要求。  
正常结束条件是：

if(k == word.length - 1){
        
          return true;
      }

非正常结束条件是：

if(i>=board.length || i<0 || j>=board[0].length || j<0 || board[i][j]!=word[k]){
        
         return false;
     }

**1.4.2对应到第二步**，标记 + 对四周进行搜索，是递归的核心过程。

char tmp = board[i][j];
     board[i][j] = ' ';
     boolean res=dfs(board, word, i+1, j, k+1) || dfs(board, word, i-1, j, k+1) 
     			|| dfs(board, word, i, j+1, k+1) || dfs(board, word, i , j-1, k+1);
                       
     board[i][j] = tmp;//保证不会影响到其他搜索路径，只暂时标记。

**1.4.3 对应到第三步**，内容已经合并在了第一步。

#### 1.5 最终代码 ####

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++) {
        
                    if(dfs(board, words, i, j, 0)){
        
                        return true;
                    } 
                }
            }
            return false;
        }
    
        boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        
            if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]){
        
                return false;
            }
            if(k == word.length - 1){
        
                return true;
            }
    
            char tmp = board[i][j];
            board[i][j] = ' ';
            boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) 
                          || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
            board[i][j] = tmp;
            return res;
        }
    }

[20200603162933781.png]: https://img-blog.csdnimg.cn/20200603162933781.png
[20200603163001357.png]: https://img-blog.csdnimg.cn/20200603163001357.png