剑指Offer——矩阵中的路径

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如
​ABCE
SFCS
ADEE
矩阵中包含一条字符串"BCCED"的路径，但是矩阵中不包含"ABCB"路径，因为字符串的第一个字符B占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

示例1
输入
"ABCESFCSADEE",3,4,"ABCCED"
返回值
true

示例2
输入
"ABCESFCSADEE",3,4,"ABCB"
返回值
false

注：
输入1：矩阵的逐行遍历字符串。
输入2、输入3：矩阵的行数、列数
输入4：目标路径

题解

DFS+回溯：从所有可能的点出发，从上下左右四个方向遍历，寻找满足条件的路径。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix string字符串 
     * @param rows int整型 
     * @param cols int整型 
     * @param str string字符串 
     * @return bool布尔型
     */
    public boolean hasPath (String matrix, int rows, int cols, String str) {
        // write code here
        // 边界
        if(matrix==null||str==null||matrix.length()==0||str.length()==0){
            return false;
        }

        boolean[][]token=new boolean[rows][cols];// 是否参与路径

        for(int i=0;i<rows;++i){
            for(int j=0;j<cols;++j){
                // 从所有点出发，然后搜索路径
                if(DFS(matrix,rows,cols,i,j,str,0,token)){
                    return true;
                }
            }
        }
        return false;

    }
    private boolean DFS(String matrix,int rows,int cols,int row,int col,String str,int index,boolean[][]token){
        // 边界
        if(row<0||row>=rows||col<0||col>=cols){
            return false;
        }

        // 当前点已经在路径中，无法继续
        if(token[row][col]){
            return false;
        }

        // 当前点不匹配
        if(matrix.charAt(cols*row+col)!=str.charAt(index)){
            return false;
        }

        // 标记加入当前路径，不重复
        token[row][col]=true;
        // 找到满足条件的路径
        if(index==str.length()-1){
            return true;
        }
        // 向4个方向扩
        boolean res=DFS(matrix,rows,cols,row-1,col,str,index+1,token)||
        DFS(matrix,rows,cols,row+1,col,str,index+1,token)||
        DFS(matrix,rows,cols,row,col-1,str,index+1,token)||
        DFS(matrix,rows,cols,row,col+1,str,index+1,token);

        // 回溯
        token[row][col]=false;
        return res;
    }
}