LeetCode 79. 单词搜索

79. 单词搜索

解题思路

在矩阵的每一个位置，都需要作为DFS的起始点去搜索最终是否能组成单词
在矩阵的每一个位置时，挑选下一个位置，可以向上下左右四个方向去选择，但前提是需要组成单词

参考代码

class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        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 ++) {
                // 判断从(i,j)位置开始，能否找到匹配的答案
                if(dfs(board, word, i, j, 0, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int row, int col, int index, boolean[][] visited) {
        // 终止条件
        if(index == word.length()) {
            return true;
        }

        int rows = board.length;
        int cols = board[0].length;

        // 判断是否相同/越界/访问过
        if(row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] != word.charAt(index) || visited[row][col]) {
            return false;
        }

        visited[row][col] = true;

        // 上下左右
        boolean found = dfs(board, word, row - 1, col, index + 1, visited)
                        || dfs(board, word, row + 1, col, index + 1, visited)
                        || dfs(board, word, row, col - 1, index + 1, visited)
                        || dfs(board, word, row, col + 1, index + 1, visited);
        
        visited[row][col] = false;
        return found;
    }
}