LeetCode-79. 单词搜索

题目来源

79. 单词搜索

题目详情

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

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

示例 1:

LeetCode-79. 单词搜索

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

示例 2:

LeetCode-79. 单词搜索

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

示例 3:

LeetCode-79. 单词搜索

输入: 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
  • boardword 仅由大小写英文字母组成

进阶: 你可以使用搜索剪枝的技术来优化解决方案,使其在 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;
            }
        }
    }
}

结果展示

LeetCode-79. 单词搜索

上一篇:有效的数独


下一篇:P2678 跳石头题解