题目来源

79. 单词搜索

题目详情

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入： board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出： true

示例 2：

输入： board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出： true

示例 3：

输入： board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出： false

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

进阶： 你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

题解分析

1. 本题很明显是深搜加回溯的题型，可以说这是一道回溯的模板题。
2. 这个题目虽然很简单，但是在编码时也会有一些细节问题，比如需要设置isTravel矩阵来标识一个坐标是否被遍历过。而且为了避免以后的轮次中重复赋初始值，需要在回溯时将isTravel重新设置为false。
3. 考虑到符合条件的单词可以从任意一个单元开始出发组成，所以需要遍历所有的矩阵单元。

class Solution {
    int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    boolean flag = false;
    boolean[][] isTravel;
    int n, m;
    public boolean exist(char[][] board, String word) {
        n = board.length;
        m = board[0].length;
        isTravel = new boolean[n][m];

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                char ch = board[i][j];
                if(ch == word.charAt(0)){
                    isTravel[i][j] = true;
                    dfs(board, word, 0, i, j);
                    isTravel[i][j] = false;
                    if(flag){
                        return true;
                    }
                }
            }
        }

        return false;
    }

    private void dfs(char[][] board, String word, int pos, int x, int y){
        if(flag){
            return;
        }
        if(pos == word.length() - 1){
            flag = true;
            return;
        }
        for(int i=0; i<4; i++){
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            if(dx >=0 && dx < n && dy >=0 && dy < m && !isTravel[dx][dy] && word.charAt(pos + 1) == board[dx][dy]){
                isTravel[dx][dy] = true;
                dfs(board, word, pos + 1, dx, dy);
                isTravel[dx][dy] = false;
            }
        }
    }
}

结果展示