個人感覺這道題其實比一般的回溯問題要難一些区匣，或者說更特殊一些
首先亏钩，一般的回溯問題，for循環(huán)都是在遞歸的外側(cè)姑丑，如此，一旦遞歸返回栅哀，會繼續(xù)循環(huán)進(jìn)行下一次遞歸称龙。更確切的說，對于當(dāng)前層痴柔，只有一個遞歸疫向。
但是這個問題for循環(huán)是為遞歸服務(wù)的，對于每一個當(dāng)前層搔驼，我們需要多個遞歸。又我們起始位置又有多個糯耍，因此還需要一個for循環(huán)，所以我們不僅在回溯函數(shù)的內(nèi)部使用for循環(huán)啦租，在外部同樣需要使用荒揣。
再一個問題就是，由于需要對下一層進(jìn)行邊界判斷系任，導(dǎo)致最后一個字母需要在if中判斷。
package No79_WordSearch;
public class Solution {
boolean[][] expored; // 走過的點
int[][] dirctions; // 方向
char[][] board;
String word;
public boolean exist(char[][] board, String word) {
int row = board.length;
int col = board[0].length;
if (row == 0 || col == 0)
return false;
expored = new boolean[row][col];
dirctions = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
this.board = board;
this.word = word;
for (int i = 0; i < row; i ++) {
for (int j = 0; j < col; j ++) {
if (traceBack(i, j, 0))
return true;
}
}
return false;
}
private boolean traceBack(int i, int j, int start) {
if (start == word.length() - 1) { // 最后一個必須在此處判斷 如果再次進(jìn)入會被continue
return board[i][j] == word.charAt(start);
}
if (board[i][j] == word.charAt(start)) {
expored[i][j] = true;
for (int k = 0; k < 4; k ++) {
int newi = i + dirctions[k][0];
int newj = j + dirctions[k][1];
if (!isValid(newi, newj) || expored[newi][newj]) {
continue;
}
if (traceBack(newi, newj, start + 1)) {
return true;
}
}
expored[i][j] = false;
}
return false;
}
private boolean isValid(int i, int j) {
return i >=0 && i < board.length && j >=0 && j < board[0].length;
}
public static void main(String[] args) {
Solution solution = new Solution();
// String word = "ABCCED";
// String word = "SEE";
// String word = "ABCB";
String word = "a";
// char[][] board = new char[][]{{'A','B','C','E'}, {'S','F','C','S'}, {'A','D','E','E'}};
char[][] board = new char[][]{{'a'}};
boolean res = solution.exist(board, word);
System.out.println(res);
}
}
如果不想在if中進(jìn)行最后一個字母的判斷 當(dāng)然也可以
package No79_WordSearch;
public class Solution2 {
boolean[][] expored; // 走過的點
int[][] dirctions; // 方向
char[][] board;
String word;
public boolean exist(char[][] board, String word) {
int row = board.length;
int col = board[0].length;
if (row == 0 || col == 0)
return false;
expored = new boolean[row][col];
dirctions = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
this.board = board;
this.word = word;
for (int i = 0; i < row; i ++) {
for (int j = 0; j < col; j ++) {
if (traceBack(i, j, 0))
return true;
}
}
return false;
}
private boolean traceBack(int i, int j, int start) {
if (start == word.length()) { // 最后一個必須在此處判斷 如果再次進(jìn)入會被continue
return true;
}
if (!isValid(i, j) || expored[i][j]) {
return false;
}
if (board[i][j] == word.charAt(start)) {
expored[i][j] = true;
for (int k = 0; k < 4; k ++) {
int newi = i + dirctions[k][0];
int newj = j + dirctions[k][1];
if (traceBack(newi, newj, start + 1)) {
return true;
}
}
expored[i][j] = false;
}
return false;
}
private boolean isValid(int i, int j) {
return i >=0 && i < board.length && j >=0 && j < board[0].length;
}
public static void main(String[] args) {
Solution2 solution = new Solution2();
// String word = "ABCCED";
// String word = "SEE";
// String word = "ABCB";
// char[][] board = new char[][]{{'A','B','C','E'}, {'S','F','C','S'}, {'A','D','E','E'}};
// String word = "a";
// char[][] board = new char[][]{{'a'}};
String word = "ABCB";
char[][] board = new char[][]{{'A','B','C','E'}, {'S','F','C','S'}, {'A','D','E','E'}};
boolean res = solution.exist(board, word);
System.out.println(res);
}
}
