【劍指offer】面試題12：矩陣中的路徑

完整代碼位址

完整代碼位址

題目

請設計一個函數，用來判斷在一個矩陣中是否存在一條包含某字元串所有字元的路徑。路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子。如果一條路徑經過了矩陣中的某一個格子，則該路徑不能再進入該格子。

例如在下面的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 ==  || str.length == ) 
        return false;

    int len = matrix.length;
    boolean[] flags = new boolean[len];

    for(int r = ; r < rows; ++r) {
        for(int c = ; c < cols; ++c) {
            if(matrix[r * cols + c] == str[]) {
                if(hasPath(matrix, rows, cols, r, c, str, , 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 <  || c >= cols || c < )
        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 + , c, str, index + , flags) ||
            hasPath(matrix, rows, cols, r - , c, str, index + , flags) ||
            hasPath(matrix, rows, cols, r, c + , str, index + , flags) ||
            hasPath(matrix, rows, cols, r, c - , str, index + , 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 = ;
    int cols = ;
    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[];
    boolean result1 = spim.hasPath(matrix1, , , new char[] {'1'}); 
    MyTest.equal(result1, false);

    char[] matrix2 = new char[] {'h','h','h','h'};
    boolean result2 = spim.hasPath(matrix2, , , new char[]); 
    MyTest.equal(result2, false);

    boolean result3 = spim.hasPath(null, , , new char[]); 
    MyTest.equal(result3, false);

    char[] matrix4 = new char[] {'h','h','h','h'};;
    boolean result4 = spim.hasPath(matrix4, , , 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, , , new char[] {'4','3','2','1'}); 
    MyTest.equal(result1, true);

    char[] matrix2 = {'1','2','3','4'};
    boolean result2 = spim.hasPath(matrix2, , , 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, , , new char[]{'a','a','a', 'a','a','a', 'a','a','a'}); 
    MyTest.equal(result3, true);
}