【剑指offer】面试题12：矩阵中的路径

电玩女神 2022-06-12 07:23 163阅读 0赞

## 完整代码地址 ##

[完整代码地址][Link 1]

## 题目 ##

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

## 思路 ##

首先找到str\[0\]字符所在位置  
判断它的路径上（上下左右）是否有str\[1\]  
以此类推，并用一个boolean数组来标识是否已经访问过某个点  
如果一条路径到某个点行不通之后，就开始回溯

## 代码 ##

public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        if(matrix == null || str == null || matrix.length == 0 || str.length == 0) 
            return false;
    
        int len = matrix.length;
        boolean[] flags = new boolean[len];
    
        for(int r = 0; r < rows; ++r) {
            for(int c = 0; c < cols; ++c) {
                if(matrix[r * cols + c] == str[0]) {
                    if(hasPath(matrix, rows, cols, r, c, str, 0, flags)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    
    private boolean hasPath(char[] matrix, int rows, int cols, int r, int c,
            char[] str, int index, boolean[] flags) {
        if(index == str.length)
            return true;
        if(r >= rows || r < 0 || c >= cols || c < 0)
            return false;
        if(flags[r * cols + c] == true || matrix[r * cols + c] != str[index])
            return false;
    
        flags[r * cols + c] = true;
    
        boolean hp = hasPath(matrix, rows, cols, r + 1, c, str, index + 1, flags) ||
                hasPath(matrix, rows, cols, r - 1, c, str, index + 1, flags) ||
                hasPath(matrix, rows, cols, r, c + 1, str, index + 1, flags) ||
                hasPath(matrix, rows, cols, r, c - 1, str, index + 1, flags);
    
        if(hp == true)
            return true;
    
        flags[r * cols + c] = false;
    
        return false;
    }

## 测试 ##

public static void main(String[] args) {
        test1();
        test2();
        test3();
    }
    
    /**
     * a  b  t  g
     * c  f  c  s
     * j  d  e  h
     * 
     * 是否包含bfce: true 
     * 是否包含abfb: false
     */
    private static void test1() {
        _12_StringPathInMatrix spim = new _12_StringPathInMatrix();
        char[] matrix = { 'a', 'b', 't', 'g',
                'c', 'f', 'c', 's', 
                'j', 'd', 'e', 'h'};
        int rows = 3;
        int cols = 4;
        boolean result1 = spim.hasPath(matrix, rows, cols, new char[] {
       'b','f','c','e'});
        MyTest.equal(result1, true);
    
        boolean result2 = spim.hasPath(matrix, rows, cols, new char[] {
       'a','b','f','b'});
        MyTest.equal(result2, false);
    }
    
    /**
     * 极端值测试
     * 1.matrix数组大小为0
     * 2.str数组大小为0 
     * 3.matrix为null
     * 4.str为null
     */
    private static void test2() {
        _12_StringPathInMatrix spim = new _12_StringPathInMatrix();
        char[] matrix1 = new char[0];
        boolean result1 = spim.hasPath(matrix1, 0, 0, new char[] {
       '1'}); 
        MyTest.equal(result1, false);
    
        char[] matrix2 = new char[] {
       'h','h','h','h'};
        boolean result2 = spim.hasPath(matrix2, 2, 2, new char[0]); 
        MyTest.equal(result2, false);
    
        boolean result3 = spim.hasPath(null, 0, 0, new char[0]); 
        MyTest.equal(result3, false);
    
        char[] matrix4 = new char[] {
       'h','h','h','h'};;
        boolean result4 = spim.hasPath(matrix4, 2, 2, null); 
        MyTest.equal(result4, false);
    }
    
    /**
     * 边界测试
     * 1.只有一行
     * 2.只有一列
     * 3.矩阵所有字母一样
     */
    private static void test3() {
        _12_StringPathInMatrix spim = new _12_StringPathInMatrix();
        char[] matrix1 = {
       '1','2','3','4'};
        boolean result1 = spim.hasPath(matrix1, 4, 1, new char[] {
       '4','3','2','1'}); 
        MyTest.equal(result1, true);
    
        char[] matrix2 = {
       '1','2','3','4'};
        boolean result2 = spim.hasPath(matrix2, 1, 4, new char[] {
       '2','3','4'}); 
        MyTest.equal(result2, true);
    
        char[] matrix3 = {
       'a','a','a', 'a','a','a', 'a','a','a'};
        boolean result3 = spim.hasPath(matrix3, 3, 3, new char[]{
       'a','a','a', 'a','a','a', 'a','a','a'}); 
        MyTest.equal(result3, true);
    }

[Link 1]: https://github.com/linpeiyou/CodingInterviews