专栏首页健程之道力扣79——单词搜索

力扣79——单词搜索

原题

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

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

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

原题url:https://leetcode-cn.com/problems/word-search/

解题

回溯

拿到这题,我一开始想到的方法就是:

  • 以每一格为起点,开始寻找,寻找的条件是要保证当前的字母和下一个和它连接的字母(上下左右)都符合条件,那么就继续查找。
  • 只要当前不符合,立刻返回 false,快速失败。
  • 利用一个二维 boolean 数组记录每一格的使用情况,记住,如果从当前格出发都不成功的话,则需要回退

接下来看看代码:

class Solution {
    // 总行数
    int row;
    // 总列数
    int col;
    // 原数组
    char[][] board;
    // 需要寻找的字符数组
    char[] wordArray;

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.row = board.length;
        this.col = board[0].length;
        this.wordArray = word.toCharArray();
                // 标记每一格是否用过的二维数组
        boolean[][] used = new boolean[row][col];

                // 以每一格为起点开始搜索
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (dfs(i, j, 0, used)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(int x, int y, int index, boolean[][] used) {
        // 当前位置是否符合条件
        if (board[x][y] != wordArray[index]) {
            return false;
        }
        // 全部找完了
        if (index == wordArray.length - 1) {
            return true;
        }
        // 设置当前格使用过了
        used[x][y] = true;

        // 寻找上下左右是否有符合下一个的情况

        // 上一格是否存在并且没有被使用过
        if (x > 0 && !used[x - 1][y]) {
            if (dfs(x - 1, y, index + 1, used)) {
                return true;
            }
        }

        // 下一格是否存在并且没有被使用过
        if (x < row - 1 && !used[x + 1][y]) {
            if (dfs(x + 1, y, index + 1, used)) {
                return true;
            }
        }

        // 左一格是否存在并且没有被使用过
        if (y > 0 && !used[x][y - 1]) {
            if (dfs(x, y - 1, index + 1, used)) {
                return true;
            }
        }

        // 右一格是否存在并且没有被使用过
        if (y < col - 1 && !used[x][y + 1]) {
            if (dfs(x, y + 1, index + 1, used)) {
                return true;
            }
        }

        // 上下左右的情况都走完了,因此回退,设置当前格没有使用过
        used[x][y] = false;

        return false;
    }
}

提交OK,执行用时:19 ms,内存消耗:38.3 MB。从时间上看起来还有不少优化的空间,那该怎么做呢?

似乎无用的优化

我看了别人更优的解法,发现思想都是一致的,只是在判断上可能会更加简洁一些,如果是判断快速失败的话,似乎没有什么本质上的区别。我将自己的写法稍微优化了一下:

class Solution {
    // 总行数
    int row;
    // 总列数
    int col;
    // 原数组
    char[][] board;
    // 需要寻找的字符数组
    char[] wordArray;

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.row = board.length;
        this.col = board[0].length;
        this.wordArray = word.toCharArray();
        // 标记每一格是否用过的二维数组
        boolean[][] used = new boolean[row][col];

        // 以每一格为起点开始搜索
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (dfs(i, j, 0, used)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(int x, int y, int index, boolean[][] used) {
        // 当前位置不存在或者使用过,则返回失败
        if (x < 0 || x >= row || y < 0 || y >= col || used[x][y]) {
            return false;
        }

        // 当前位置是否符合条件
        if (board[x][y] != wordArray[index]) {
            return false;
        }
        // 全部找完了
        if (index == wordArray.length - 1) {
            return true;
        }
        // 设置当前格使用过了
        used[x][y] = true;

        // 寻找上下左右是否有符合下一个的情况
        boolean flag = dfs(x - 1, y, index + 1, used) || dfs(x + 1, y, index + 1, used) ||
                        dfs(x, y - 1, index + 1, used) || dfs(x, y + 1, index + 1, used);

        // 上下左右的情况都走完了,因此回退,设置当前格没有使用过
        used[x][y] = false;

        return flag;
    }
}

提交OK,执行用时:5 ms,内存消耗:38.4 MB。用时上少了很多,应该在于判断上:

  • 针对位置是否存在的判断,之前的写法是判断下一个位置是否存在,分散在四个 if 判断中,现在是写在一个里面,用于判断当前位置。
  • 寻找上下左右时,因为逻辑运算||是支持短路的,所以和之前分在四个 if 中效果是差不多的,但看起来更加简洁。

好吧,其实我自己也没有看懂为什么这样写时间上会减少,大家如果知道的话,欢迎在下方留言。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题主要就是回溯,针对边界情况需要注意,应该就没有其他问题了。

有兴趣的话可以访问我的博客或者关注我的公众号,说不定会有意外的惊喜。

https://death00.github.io/

本文分享自微信公众号 - 健程之道(JianJianCoder),作者:健健壮

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 力扣240——搜索二维矩阵

    编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:

    健程之道
  • 力扣289——生命游戏

    根据 百度百科 ,生命游戏,简称为生命,是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

    健程之道
  • Java面试-动态规划与组合数

    最近在刷力扣上的题目,刷到了65不同路径,当初上大学的时候,曾在hihocoder上刷到过这道题目,但是现在已经几乎全忘光了,大概的知识点是动态规划,如今就让我...

    健程之道
  • 【Leetcode】【python】Arranging Coins

    你有n枚硬币,想要组成一个阶梯形状,其中第k行放置k枚硬币。 给定n,计算可以形成的满阶梯的最大行数。 n是非负整数,并且在32位带符号整数范围之内。

    后端技术漫谈
  • 数据结构基础-递归和循环技巧

    递归是从数学领域的数学归纳法借鉴过来的一种技术。递归代码通常比迭代代码更加简洁易懂。当任务能够被相似的子任务定义时,采用递归处理十分有效。二分排序和遍历等问题往...

    1025645
  • 回溯:系列经典题目

    对于回溯算法,一开始接触感觉还是挺难的,随着刷到的题目的数量增多,慢慢也可以总结出来相应的套路出来。大家一起来看看下面的伪代码

    鹏-程-万-里
  • Climbing Stairs

    问题:上楼每次能走一步或两步,有多少种走法 class Solution { public: int a[1000]; int dfs(int ...

    用户1624346
  • hdu1021

    @坤的
  • 最大公约数和最小公倍数及其应用(Go语言解法)

    image.png 最大公约数(greatest common divisor)欧几里得辗转相除法:gcd(x,y)表示x和y的最大公约数进入运算时:x!=0,...

    李海彬
  • 【leetcode算法-搜索插入位置】

    给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

    用户5640963

扫码关注云+社区

领取腾讯云代金券