题目描述(中等难度)

意思就是从某个字符出发,然后它可以向左向右向上向下移动,走过的路径构成一个字符串,判断是否能走出给定字符串的 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,题目就迎刃而解了。异或的应用很强。

results matching ""

    No results matching ""