题目要求：
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
解题思路及代码实现：
- 当矩阵中坐标为 (row, col) 的元素和路径字符串 str 中下标为 pathLength 的字符相同时，从 4 个相邻的元素 (row, col - 1) (左)、(row - 1, col) (上)、(row, col + 1) (右)、(row + 1, col) (下) 中去搜索路径字符串中下标为 pathLength + 1 的字符
- 若 4 个相邻的元素都没有匹配字符串中下标为 pathLength + 1 的字符，则回到前一个字符 (下标为 pathLength - 1)，重新搜索
- 重复以上过程，直到匹配路径字符串中的所有字符为止 (str.length == pathLength)
判断在一个矩阵中是否存在一条包含某字符串所有字符的路径:
// 矩阵中左、右、上、下 的坐标变化
private final static int[][] nextStr = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
// 矩阵行数
private int rows;
// 矩阵列数
private int cols;
/**
* 判断在一个矩阵中是否存在一条包含某字符串所有字符的路径
*
* @param array 要转换为矩阵的数组
* @param rows 矩阵行数
* @param cols 矩阵列数
* @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;
}
创建矩阵：
/**
* 创建矩阵
* @param array 矩阵中的所有字符构成的一维数组
* @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
}
