個人感覺這道題其實比一般的回溯問題要難一些，或者說更特殊一些

首先，一般的回溯問題，for循環(huán)都是在遞歸的外側(cè)，如此，一旦遞歸返回，會繼續(xù)循環(huán)進行下一次遞歸。更確切的說，對于當前層，只有一個遞歸。
但是這個問題for循環(huán)是為遞歸服務(wù)的，對于每一個當前層，我們需要多個遞歸。又我們起始位置又有多個，因此還需要一個for循環(huán)，所以我們不僅在回溯函數(shù)的內(nèi)部使用for循環(huán)，在外部同樣需要使用。

再一個問題就是，由于需要對下一層進行邊界判斷，導致最后一個字母需要在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) { // 最后一個必須在此處判斷 如果再次進入會被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中進行最后一個字母的判斷 當然也可以

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()) { // 最后一個必須在此處判斷 如果再次進入會被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);
    }
}

題解傳送門