LeetCode-79 单词搜索

用户3470542

发布于 2019-06-26 16:22:24

5720

发布于 2019-06-26 16:22:24

文章被收录于专栏：算法半岛算法半岛

> 题目：79. 单词搜索

> 难度：中等

> 分类：数组

> 解决方案：DFS、回溯算法

今天我们学习第79题单词搜索，这个题目是一个典型的DFS，经常出现笔试中，而且模板很固定，最好要熟练掌握。我们先看看这道题的题目描述。

题目描述

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

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

示例:

board =[  ['A','B','C','E'],  ['S','F','C','S'],  ['A','D','E','E']]
给定 word = "ABCCED", 返回 true.给定 word = "SEE", 返回 true.给定 word = "ABCB", 返回 false.

分析

这个题目是让我们在一个二维网格中通过给定的规则进行搜索word是否存在，是一个典型的深度优先遍历（DFS）的应用。

对于二维网格中的每一个字符，如果该字符是word对应查找的字符，我们接下来继续判断网格中的该字符的上下左右字符是否为word对应的下一个字符，直到匹配完成。对于示例的详细分析过程如下：

对于上述分析不难，难点在于如何实现对搜索过程中的判断，这里涉及到DFS和回溯算法，对这个知识点不太清楚的小伙伴可以扫描文章下方的二维码，关注『算法半岛』回复『数据结构目录』，即可获得相关学习资料。

上述分析所对应的 java代码如下所示：

class Solution {    public boolean exist(char[][] board, String word) {        // 特殊情况判断        if(board == null || board.length == 0)            return false;
        int rows = board.length;        int cols = board[0].length;
        // 申请并初始化visited数组        boolean[][] visited = new boolean[rows][cols];
        // 从二维网格的左上角开始于word的首字符进行判断        for(int i=0; i<rows; ++i){            for(int j=0; j<cols; ++j){                if(dfs(board, word, 0, i, j, visited))  // 判断函数                    return true;            }        }        return false;    }
    // 判断函数    private boolean dfs(char[][] board, String word, int idx, int i, int j, boolean[][] visited){        // 当单词判断结束后，直接返回true        if(idx == word.length())            return true;        int rows = board.length;        int cols = board[0].length;
        // 边界条件处理        // 或字符已经访问处理        // 或word中的字符与二维网格中的字符不相等 直接返回false        if(i<0 || j<0 || i>=rows || j>=cols            || visited[i][j]           || word.toCharArray()[idx] != board[i][j]){            return false;        }
        // word中的字符与二维网格中的字符相等即修改visited对应位置为true        visited[i][j] = true;
        // 判断word下一个字符与二维网格中已判断的字符的上下左右四个相邻字符是否有一个相等的字符        // 如果相等，则继续进入深度遍历进行判断        boolean res = dfs(board, word, idx+1, i-1, j, visited)                    || dfs(board, word, idx+1, i+1, j, visited)                    || dfs(board, word, idx+1, i, j-1, visited)                    || dfs(board, word, idx+1, i, j+1, visited);
        // 如果不相等，回溯        visited[i][j] = false;        return res;    }}