78.单词搜索

个人感觉这道题其实比一般的回溯问题要难一些，或者说更特殊一些

首先，一般的回溯问题，for循环都是在递归的外侧，如此，一旦递归返回，会继续循环进行下一次递归。更确切的说，对于当前层，只有一个递归。
但是这个问题for循环是为递归服务的，对于每一个当前层，我们需要多个递归。又我们起始位置又有多个，因此还需要一个for循环，所以我们不仅在回溯函数的内部使用for循环，在外部同样需要使用。

再一个问题就是，由于需要对下一层进行边界判断，导致最后一个字母需要在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);
    }
}

题解传送门