題目要求：

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

解題思路及代碼實現(xiàn)：

1. 當(dāng)矩陣中坐標(biāo)為 (row, col) 的元素和路徑字符串 str 中下標(biāo)為 pathLength 的字符相同時，從 4 個相鄰的元素 (row, col - 1) (左)、(row - 1, col) (上)、(row, col + 1) (右)、(row + 1, col) (下) 中去搜索路徑字符串中下標(biāo)為 pathLength + 1 的字符
2. 若 4 個相鄰的元素都沒有匹配字符串中下標(biāo)為 pathLength + 1 的字符，則回到前一個字符 (下標(biāo)為 pathLength - 1)，重新搜索
3. 重復(fù)以上過程，直到匹配路徑字符串中的所有字符為止 (str.length == pathLength)

判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑:

    // 矩陣中左、右、上、下 的坐標(biāo)變化
    private final static int[][] nextStr = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

    // 矩陣行數(shù)
    private int rows;

    // 矩陣列數(shù)
    private int cols;

/**
     *  判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑
     *
     * @param array  要轉(zhuǎn)換為矩陣的數(shù)組
     * @param rows   矩陣行數(shù)
     * @param cols   矩陣列數(shù)
     * @param str    要查找的字符串
     * @return true or false
     */
    private boolean hasPath(char[] array, int rows, int cols, char[] str) {
        if (rows == 0 || cols == 0 || array == null) {
            return false;
        }
        this.rows = rows;
        this.cols = cols;

        boolean[][] visited = new boolean[rows][cols];
        char[][] matrix = createMatrix(array);
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (backTracking(matrix, i, j, visited, str, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

回溯法搜索路徑中的下一個字符:

/**
     * 回溯法搜索下一個字符
     *
     * @param matrix
     * @param row
     * @param col
     * @param visited
     * @param str
     * @param pathLength
     * @return
     */
    private boolean backTracking(char[][] matrix, int row, int col, boolean[][] visited,
                                 char[] str, int pathLength) {
        
        // 字符串 str 中的所有字符都在 matrix 中找到時返回 true
        if (pathLength == str.length) {
            return true;
        }

        if (row < 0 || row >= rows || col < 0 || col >= cols
                || matrix[row][col] != str[pathLength] || visited[row][col]) {
            return false;
        }

        visited[row][col] = true;
        for (int[] n : nextStr) { // 回溯搜索的順序 --> 左、右、上、下 
            if (backTracking(matrix, row + n[0], col + n[1], visited, str, pathLength + 1)) {
                return true;
            }
        }

        visited[row][col] = false;
        return false;
    }

創(chuàng)建矩陣：

/**
     * 創(chuàng)建矩陣
     * @param array 矩陣中的所有字符構(gòu)成的一維數(shù)組
     * @return
     */
private char[][] createMatrix(char[] array) {
        char[][] matrix = new char[rows][cols];
        for (int i = 0, index = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                matrix[i][j] = array[index++];
            }
        }
        return matrix;
    }

測試代碼：

    @Test
    public void test() {
        HasPathInMatrix matrix = new HasPathInMatrix();

        char[] array = {'a', 'b', 't', 'g', 'c', 'f', 'c', 's', 'j', 'd', 'e', 'h'};

        // 矩陣中不存在路徑
        char[] str = {'b', 'f', 'c', 'g'};
        boolean hasPath = matrix.hasPath(array, 3, 4, str);
        System.out.println(hasPath); // false

        // 矩陣中存在路徑
        char[] str1 = {'b', 'f', 'c', 'e'};
        boolean hasPath1 = matrix.hasPath(array, 3, 4, str1);
        System.out.println(hasPath1); // true

        // 輸入空指針
        char[] str4 = {'b', 'f', 'c', 'g'};
        boolean hasPath4 = matrix.hasPath(null, 3, 4, str4);
        System.out.println(hasPath4); // false

        // 矩陣只有一行,且矩陣和路徑中的所有字母都相同
        char[] arr = {'z', 'j', 'c', 'z', 'y'};
        char[] str2 = {'z', 'j', 'c', 'z', 'y'};
        boolean hasPath2 = matrix.hasPath(arr, 1, 5, str2);
        System.out.println(hasPath2); // true

        // 矩陣只有一列,且矩陣和路徑中的所有字母都相同
        char[] str3 = {'z', 'j', 'c', 'z', 'y'};
        boolean hasPath3 = matrix.hasPath(arr, 5, 1, str3);
        System.out.println(hasPath3); // true
    }