題目要求：
請設計一個函數(shù)泳秀，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個格子開始哆键，每一步可以在矩陣中向左，向右瘦锹，向上籍嘹，向下移動一個格子。如果一條路徑經(jīng)過了矩陣中的某一個格子弯院，則該路徑不能再進入該格子辱士。
解題思路及代碼實現(xiàn)：
- 當矩陣中坐標為 (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}};
// 矩陣行數(shù)
private int rows;
// 矩陣列數(shù)
private int cols;
/**
* 判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑
*
* @param array 要轉換為矩陣的數(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 矩陣中的所有字符構成的一維數(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
}
