leetCode-79-Word-Search.md

题目描述（中等难度）

意思就是从某个字符出发，然后它可以向左向右向上向下移动，走过的路径构成一个字符串，判断是否能走出给定字符串的 word ，还有一个条件就是走过的字符不能够走第二次。

比如 SEE，从第二行最后一列的 S 出发，向下移动，再向左移动，就走出了 SEE。

ABCB，从第一行第一列的 A 出发，向右移动，再向右移动，到达 C 以后，不能向左移动回到 B ，并且也没有其他的路径走出 ABCB 所以返回 false。

解法一 DFS

我们可以把矩阵看做一个图，然后利用图的深度优先遍历 DFS 的思想就可以了。

我们需要做的就是，在深度优先遍历过程中，判断当前遍历元素是否对应 word 元素，如果不匹配就结束当前的遍历，返回上一次的元素，尝试其他路径。当然，和普通的 dfs 一样，我们需要一个 visited 数组标记元素是否访问过。

public boolean exist(char[][] board, String word) {
    int rows = board.length;
    if (rows == 0) {
        return false;
    }
    int cols = board[0].length;
    boolean[][] visited = new boolean[rows][cols];
    //从不同位置开始
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            //从当前位置开始符合就返回 true
            if (existRecursive(board, i, j, word, 0, visited)) {
                return true;
            }
        }
    }
    return false;
}

private boolean existRecursive(char[][] board, int row, int col, String word, int index, boolean[][] visited) {
    //判断是否越界
    if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
        return false;
    }
    //当前元素访问过或者和当前 word 不匹配返回 false
    if (visited[row][col] || board[row][col] != word.charAt(index)) {
        return false;
    }
    //已经匹配到了最后一个字母，返回 true
    if (index == word.length() - 1) {
        return true;
    }
    //将当前位置标记位已访问
    visited[row][col] = true;
    //对四个位置分别进行尝试
    boolean up = existRecursive(board, row - 1, col, word, index + 1, visited);
    if (up) {
        return true;
    }
    boolean down = existRecursive(board, row + 1, col, word, index + 1, visited);
    if (down) {
        return true;
    }
    boolean left = existRecursive(board, row, col - 1, word, index + 1, visited);
    if (left) {
        return true;
    }
    boolean right = existRecursive(board, row, col + 1, word, index + 1, visited);
    if (right) {
        return true;
    }
    //当前位置没有选进来，恢复标记为 false
    visited[row][col] = false;
    return false; 
}

我们可以优化一下空间复杂度，我们之前是用了一个等大的二维数组来标记是否访问过。其实我们完全可以用之前的 board，我们把当前访问的元素置为 "$" ，也就是一个在 board 中不会出现的字符。然后当上下左右全部尝试完之后，我们再把当前元素还原就可以了。

public boolean exist(char[][] board, String word) {
    int rows = board.length;
    if (rows == 0) {
        return false;
    }
    int cols = board[0].length;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (existRecursive(board, i, j, word, 0)) {
                return true;
            }
        }
    }
    return false;
}

private boolean existRecursive(char[][] board, int row, int col, String word, int index) {
    if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
        return false;
    }
    if (board[row][col] != word.charAt(index)) {
        return false;
    }
    if (index == word.length() - 1) {
        return true;
    }
    /*********************改变的地方****************************************/
    char temp = board[row][col];
    board[row][col] = '$';
    /*********************************************************************/
    boolean up = existRecursive(board, row - 1, col, word, index + 1);
    if (up) {
        return true;
    }
    boolean down = existRecursive(board, row + 1, col, word, index + 1);
    if (down) {
        return true;
    }
    boolean left = existRecursive(board, row, col - 1, word, index + 1);
    if (left) {
        return true;
    }
    boolean right = existRecursive(board, row, col + 1, word, index + 1);
    if (right) {
        return true;
    }
    /*********************改变的地方****************************************/
    board[row][col] = temp;
    /*********************************************************************/
    return false;
}

在这里，看到另外一种标记和还原的方法。异或。

/*********************之前的做法****************************************/
char temp = board[row][col];
board[row][col] = '$';
/*********************************************************************/

/*********************利用异或****************************************/
board[row][col] ^= 128;
/*********************************************************************/

//还原
/********************之前的做法****************************************/
board[row][col] = temp;
/*********************************************************************/

/*********************利用异或****************************************/
board[row][col] ^= 128;
/*********************************************************************/

至于原理，因为 ASCII 码值的范围是 0 - 127，二进制的话就是 0000 0000 - 0111 1111，我们把它和 128 做异或，也就是和 1000 0000 。这样，如果想还原原来的数字只需要再异或 128 就可以了。

其实原理是一样的，都是把之前的数字变成当前 board 不存在的字符，然后再变回来。只不过这里考虑它的二进制编码，在保留原有信息的基础上做改变，不再需要 temp 变量。

总

关键是对题目的理解，抽象到 DFS，题目就迎刃而解了。异或的应用很强。