LeetCode 79 单词搜索 | 解题思路分享

原题链接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 更大的情况下可以更快解决问题

---

解题思路

这道题可以用深度优先搜索来解题目的意思是行走过程中拼成的单词要等于题目给出的单词然后让我们找一条这样的行走路径。

可以这样去转化

• 起点仍然是固定的就是在网格中与单词第一个字母相同的格子可能有多个起点可以通过遍历网格找到。
• 从起点往四周去寻找哪个方向能走取决于网格的内容是否与单词的字母相同但同一个格子不能走两次。

这其实就很容易看出来了就是一道迷宫题深度优先搜索就可以应对。

假设我们现在从起点记为x , y出发当前要找的内容为单词的第一个字母第几个记为index那么具体思路

1. 设置递归的终止条件按序号判断

   1. 如果当前格子的值不等于单词的第一个字母那肯定没戏了直接返回false吧
   2. 如果当前要找的字母已经是单词的最后一个字母了那说明我们已经找完了呀那直接返回true了。

2. 没满足终止条件那说明我们已经走在当前这个格子上了而且还得往后继续走那我们得标记一下防止后面重复走了这个格子。就创建一个flag二维数组好了大小刚好为网格的大小可以标记到每一个网格

   现在我们把flag[x][y]设置为true。

3. 好了那我们得继续往后面探索了先看看四周的格子能走吗

   • 首先得考虑下我们是不是在地图边界了如果在地图边界的话那有些方向就不能走了不然我就越界了这很不好。
   • 其次我们还得考虑下哪些方向的格子是走过的哪些是没走过的。记得我们刚刚用 flag 二维数组来记录了所有走过的格子所以我只要判断下四周的位置在flag里哪些的值是false只有这些地方是可以进一步探索的。

4. 我已经确定好要走哪些格子了那我得往后走了。递归的时候我得把下一个位置的坐标传过去还有标记着已经走过路径的flag数组。也千万别忘了告诉下一层递归它要找的字母就是我刚找到的那个字母的下一个index + 1。

5. 递归的过程中会重复我们上面的步骤当递归结束回来的时候也会带回来我们在第一步设置的返回条件找到了就是true没找到就是false。

   那虽然我们同时往几个方向都走过了但只要其中一个方向返回true就说明有一条路径是符合条件的那我们就返回true要是都没找到那我们就返回false。

这段解题思路比较冗长且无聊建议结合下面的核心代码一起理解

核心代码

char[][] board; // 网格由题目提供数据
String word; // 要找的单词题目提供

int[] sitx = {-1,0,1,0}; // 用来走格子的方向可以减少重复代码
int[] sity = {0,-1,0,1};

// x和y表示当前坐标
// index表示当前已经走到第几个字母了
// flag表示已经走过的路径其中走过的值为true
boolean find(int x, int y, int index ,boolean[][] flag) {
    // 如果当前格子的字母不是要找的直接返回false
    if (word.charAt(index) != board[x][y]) {
        return false;
    }
    // 已经找到最后一个字母了直接返回true
    if (index == word.length() - 1) {
        return true;
    }
    // 当前这个格子已经走了给flag赋值
    flag[x][y] = true;
    for (int i = 0 ; i < 4; i++) {
        // 下一步要走的位置nextx、nexty
        int nx = x + sitx[i];
        int ny = y + sity[i];

        // 判断是否超过边界以及是否已经走过
        boolean isEdge = nx == -1 || nx == board.length || ny == -1 || ny == board[0].length;
        if (isEdge || flag[nx][ny]) continue;

        // 如果没有走过就往这个方向走
        boolean isFand = find(nx, ny, index + 1, flag);
        // 如果找到了直接返回
        if (isFand) return true;

    }
    // 没有找到格式的路径返回上一级之前记得清理flag
    flag[x][y] = false;
    return false;
}

好交一发当然通过了但速度不快应该还能优化但我看官方题解却没有看到优化方法。

完整解题代码 Java

class Solution {
    public boolean exist(char[][] board, String word) {
        int n = board.length;
        int m = board[0].length;
        this.word = word;
        this.board = board;
        // 寻找起点并开启第一步
        for (int i = 0 ; i < n; i++ ) {
            for (int j = 0 ; j < m ; j++) {
                if (board[i][j] == word.charAt(0)) {
                    boolean isFand = find(i, j, 0, new boolean[n][m]);
                    if (isFand) return true;
                }
            }
        }

        return false;
    }

    // 把上面的核心代码放在这即可

}

由于上面已经贴了核心代码了所以这里我就只贴了其他的部分如果要提交到LeetCode进行测试的话记得要把前面的核心代码贴过来噢。