☆打卡算法☆LeetCode 79、单词搜索 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个二维数组和一个单词，如果单词存在网格中返回true，否则返回false。”

题目链接：

来源：力扣（LeetCode）

链接：79. 单词搜索 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给定一个 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

二、解题

1、思路分析

类似找出所有可能解的问题，首先就可以想到用回溯算法。

这道题意思是从网格(i,j)开始搜索，找到单词word[k…]，如果搜索到就返回true，不然就返回false。

理一下思路就是：

• 遍历搜索，网格(i,j)≠单词[k]，那么这个字符就是不匹配的，返回false
• 如果已经搜索到单词末尾，但是字符依旧是匹配的状态，返回true，否则返回false
• 通过当前位置，搜索所有相邻位置，然后根据相邻位置搜索所有子串，找到返回true，否则返回false

2、代码实现

代码参考：

class Solution {
    public boolean exist(char[][] board, String word) {
        int h = board.length, w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                boolean flag = check(board, visited, i, j, word, 0);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
        if (board[i][j] != s.charAt(k)) {
            return false;
        } else if (k == s.length() - 1) {
            return true;
        }
        visited[i][j] = true;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean result = false;
        for (int[] dir : directions) {
            int newi = i + dir[0], newj = j + dir[1];
            if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                if (!visited[newi][newj]) {
                    boolean flag = check(board, visited, newi, newj, s, k + 1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return result;
    }
}

3、时间复杂度

时间复杂度 ： O(M N · 3^L)

M，N是网格的长度和宽度，L是单词的长度。

空间复杂度： O(M N)

只需要使用一个临时数组O(MN)的空间即可。

三、总结

这道题使用了回溯算法去解题，其实对于这道题还有优化算法，那就是剪枝，遇到不匹配或已访问的字符时提前退出，可以提高算法的效率。

这也是深度优先搜索的思想，可以对使用过元素进行标记，标记完进入递归，在递归中进行字符匹配。