剑指Offer-矩阵中的路径

青旅半醒 2022-04-25 05:58 156阅读 0赞

## 题目描述 ##

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

解题思路—**回溯法-递归版**：`这是一题使用回溯法解决的经典题目。`

> 为了**判别当前路径有没有走过**，需要建立一个与matrix一样大的**标志位数组**，**初始化为false**，表示**未走过**；**true**表示当前路径**已走过**。  
> **先在矩阵中匹配到字符串的头字符，然后进行递归，从4个相邻的格子(row,col-1)，(row-1,col)，(row,col+1)以及(row+1,col)中去定位路径字符串中的下一个字符。如果4个相邻的格子都没有匹配字符串中下一个的字符，表明当前路径字符串中字符在矩阵中的定位不正确，需要返回到前一个字符，然后重新定位。**  
> **递归的终止条件**有**数组的越界**、**字符不匹配**以及**路径已经遍历过**，还有一个就是**字符串已经匹配完成**。  
> 要注意回溯的时候**不要**使用 **row++,row–,col++,col–** 等，这样会在当前连续的判断中改变row和col的值。

解题思路—**回溯法-非递归版**：核心思想与递归版一样，只不过**使用堆栈同步存储已经走过的路径**进行判断。同时也要**注意数组越界判断、字符串回退**等。

## Java解题—回溯法-递归版 ##

public class Solution {
        public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
        {
            boolean[] isExist = new boolean[rows*cols];
            for(int i=0;i<rows;i++)
                for(int j=0;j<cols;j++)
                    // 匹配字符串的头
                    if(isMatch(matrix, rows, cols, str, i, j, isExist, 0))
                        return true;
    
             return false;
        }
        
        public boolean isMatch(char[] matrix, int rows, int cols, char[] str, int i, int j, boolean[] isExist, int strstart){
            if(i<0 || j<0 || i>=rows || j>=cols || matrix[i*cols+j]!=str[strstart] || isExist[i*cols+j])
                return false;
    
            // 字符串匹配结束
            if(strstart==str.length-1)
                return true;
    
            // 标识走过的路
            isExist[i*cols+j] = true;
    
            // 进行回溯，上下左右
            if(isMatch(matrix, rows, cols, str, i-1, j, isExist, strstart+1)
                    || isMatch(matrix, rows, cols, str, i+1, j, isExist, strstart+1)
                    || isMatch(matrix, rows, cols, str, i, j-1, isExist, strstart+1)
                    || isMatch(matrix, rows, cols, str, i, j+1, isExist, strstart+1))
                return true;
    
            // 回退这一格
            isExist[i*cols+j] = false;
            return false;
        }
    }

## Java解题—回溯法-非递归版 ##

import java.util.Stack;
    public class Solution {
        public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
        {
            if(matrix == null || matrix.length != rows * cols || str == null || str.length == 0 || str.length > matrix.length)
                return false;
            boolean[] isExist = new boolean[rows*cols];
    
            for(int i=0;i<rows;i++)
                for(int j=0;j<cols;j++)
                    // 匹配字符串的头
                    if(matrix[i*cols+j]==str[0])
                        if(isMatch(matrix, rows, cols, str, i, j, isExist))
                            return true;
    
             return false;
        }
        
        // 遍历上下左右
        private static int[] x = {0,1,0,-1};
        private static int[] y = {1,0,-1,0};
        
        public boolean isMatch(char[] matrix, int rows, int cols, char[] str, int i, int j, boolean[] isExist){
            Stack<Integer> stack = new Stack<>(); // 存放路径
    
            int strstart= 0;
            stack.push(i*cols+j);
    
            while(!stack.empty()){
                int loc = stack.peek();
                if(isExist[loc]){
                    isExist[loc] = false; // 回退这一格
                    stack.pop(); // 退出该节点
                    if(--strstart<0)
                        return false;
                    continue; // 防止再次遍历该路径
                }
                isExist[loc] = true; // 标识走过的路
                // 字符串匹配结束
                if(strstart==str.length-1)
                    return true;
                
                strstart++;
                // 进行回溯，上下左右
                for(int t=0;t<4;t++){
                    int xn = loc / cols + x[t];
                    int yn = loc % cols + y[t];
                    int cur = xn*cols + yn;
                    if(xn>=0 && xn<rows && yn>=0 && yn<cols && !isExist[cur] && matrix[cur]==str[strstart])
                        stack.push(cur);
                }
    
            }
            return false;
        }
    }