剑指 Offer 12. 矩阵中的路径

朱雀 2022-12-17 02:27 24阅读 0赞

# 题目 #

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。  
![在这里插入图片描述][20201021154713127.png_pic_center]  
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

示例 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

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof][https_leetcode-cn.com_problems_ju-zhen-zhong-de-lu-jing-lcof]

# 解题思路 #

本题思路:深度优先遍历dfs+剪枝

使用一个二维数组来标识当前位置字符是否已使用  
回溯基本步骤:

*  将当前位置字符标记为已使用
 *  向上下左右四个方向进行查找
 *  撤销使用标识

dfs结束条件

*  下标越界
 *  当前位置字符已使用
 *  当前位置字符不相等
 *  当前位置字符相等,且为字符串最后一个字符

# 代码 #

class Solution { 
        public boolean exist(char[][] board, String word) { 
            // 本题思路: 深度优先遍历dfs + 剪枝
            int rows = board.length;
            int cols = board[0].length;
            // 初始化一个数组,用来标记当前字符是否已使用
            boolean[][] used =  new boolean[rows][cols];
    
            for (int row = 0; row < rows; row++) { 
                for (int col = 0; col < cols; col++) { 
                    if (recur(board, row, col, rows, cols, word, 0, used)) { 
                        return true;
                    }
                }
            }
    
            return false;
        }
    
        private boolean recur(char[][] board, int row, int col, int rows, int cols, String word, int index, boolean[][] used) { 
            // 判断下标是否越界,当前字符是否已使用,当前位置字符是否相等
            if (row < 0 || row >= rows || col < 0 || col >= cols || used[row][col] || board[row][col] != word.charAt(index)) {  
                return false;
            }
    
            // 判断是不是最后一个字符
            if (index == word.length() - 1) { 
                return true;
            }
    
            // 标记当前位置字符已使用
            used[row][col] = true;
            // 向四个方法进行查找
            boolean flag = recur(board, row + 1, col, rows, cols, word, index + 1, used) 
                        || recur(board, row - 1, col, rows, cols, word, index + 1, used)
                        || recur(board, row, col + 1, rows, cols, word, index + 1, used)
                        || recur(board, row, col - 1, rows, cols, word, index + 1, used);
            // 撤销使用标识
            used[row][col] = false;
            return flag;
        }
    }

[20201021154713127.png_pic_center]: /images/20221123/49e566029e68432bb1e1c27638e36096.png
[https_leetcode-cn.com_problems_ju-zhen-zhong-de-lu-jing-lcof]: https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof