JZ12 矩阵中的路径

JZ12 矩阵中的路径

描述

请设计一个函数,用来判断在一个n乘m的矩阵中是否存在一条包含某长度为 len 的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。

JZ12 矩阵中的路径

例如矩阵中包含一条字符串 “bcced” 的路径,但是矩阵中不包含 “abcb” 路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

数据范围:0 ≤ n,m ≤ 20,1 ≤ len ≤ 25

进阶:时间复杂度O(n2),空间复杂度O(n2 )

示例1

输入:

[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcced"

返回值:

true

示例2

输入:

[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcb"

返回值:

false

解析

初见这种题目,属实有点迷茫。在看了会书后获得了思路,程序的执行逻辑应该为:

  1. 通过遍历矩阵,以每个位置都作为起点尝试寻找路径
  2. 寻找路径时,判断当前节点是否对应上了当前所需字符;
  3. 若对应上了,则在上下左右四条路径中寻找下一个字符;
    1. 若四条路径都走不通,说明当前节点其实是个死胡同,此时需要回溯到上一个节点(回溯法,要复原当前节点造成的变化),并返回 false 表明当前节点走不通;
    2. 若四条路径中某条能走通,则在能走通的路径中继续寻找路径,若后续能走通,则当前节点是有效的,可以返回 true
  4. 若没对应上,则说明当前节点走不通,返回 false
  5. 若当前节点没有对应的字符,说明路径走完了,寻找到了有效路径,可以返回 true

从分析问题时可以注意到,这是一个子结构相似的问题,即都是以某一点探索周围的四条路径,是典型的递归问题

分析完程序的执行逻辑后,还要进行边界情况的考虑:

  1. 寻找当前节点周围的四条路径时,若当前节点处于矩阵的边上,则有一条路径是无效的,需要进行判断直接返回 false,否则会造成数组越界异常;
  2. 题中所述,不能走已经走过的节点,所以需要引入 visited 布尔型数组,大小与矩阵相同,用以表示矩阵中的某个位置是否走过。到达某节点时先进行判断,若该节点已走过,直接返回 false

代码清单

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    // 回溯法
    public boolean hasPath (char[][] matrix, String word) {
        // 矩阵行数,
        int rows = matrix.length;
        // 矩阵列数
        int cols = matrix[0].length;
        // 标记当前为第几个字符
        int strNum = 0;
        // 方便获取字符
        char[] words = word.toCharArray();
        // 是否访问过矩阵
        boolean[][] visited = new boolean[rows][cols];
        // 遍历矩阵,从每个点都开始寻找路径
        for(int r = 0;r < rows;r++){
            for(int c = 0; c < cols;c++){
                if(hasPathCore(matrix,words,strNum,r,c,visited)){
                    // 找到路了
                    return true;
                }
            }
        }
        // 遍历完都没找到,那就是没有
        return false;
    }
    
    public boolean hasPathCore(char[][] matrix,char[] words,int strNum,
                              int row,int col,boolean[][] visited){
        // 重要!!!递归停止条件!!!
        if( strNum == words.length)
            return true;
        // 标记
        boolean flag = false;
        // 矩阵行数,
        int rows = matrix.length;
        // 矩阵列数
        int cols = matrix[0].length;
        // 先进行边界情况的判断
        if(row<0 || col<0 || row >= rows ||col >= cols || visited[row][col]==true)
            return flag;
        // 若当前节点走的通!
        if(matrix[row][col] == words[strNum]){
            // 走下一个点
            strNum++;
            // 当前点设为走过
            visited[row][col] = true;
            // 四个方向 寻找后面的路
            flag = hasPathCore(matrix,words,strNum,row+1,col,visited)
                || hasPathCore(matrix,words,strNum,row-1,col,visited)
                || hasPathCore(matrix,words,strNum,row,col+1,visited)
                || hasPathCore(matrix,words,strNum,row,col-1,visited);
            
            // 只有能找到后面的路时,这个节点才是有效路径,否则要回溯
            if(flag==false){
                strNum--;
                visited[row][col] = false;
            }
        }
        return flag;
    }
}

之前想到的一个疑问:一个节点要找它周围的四条路,有没有可能寻路过程中它们会撞上?

答案是不会,因为递归在程序中其实是按顺序执行的,即按照定义好的方向如上下左右,就会先找上面的路,再到下面的路,以此类推,若当前路径走不通了,则会回溯到之前的状态,不会对后面的寻路造成影响。

总结

第一次写回溯法相关的题目,想不到思路也很正常,但其实还是比较简单的。

上一篇:【面试刷题】宽度优先搜索


下一篇:【每日一题见微知著】Hash表+BFS—— 跳跃游戏 IV-Hard(今天这个难度对了)