力扣每日一题79:单词搜索

这篇具有很好参考价值的文章主要介绍了力扣每日一题79:单词搜索。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述:

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

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

示例 1:

力扣每日一题79:单词搜索,LeetCode每日一题,leetcode,c#,算法

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

示例 2:

力扣每日一题79:单词搜索,LeetCode每日一题,leetcode,c#,算法

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

示例 3:

力扣每日一题79:单词搜索,LeetCode每日一题,leetcode,c#,算法

输入: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 更大的情况下可以更快解决问题?

通过次数

462.9K

提交次数

997.8K

通过率

46.4%

思路和题解:

回溯和剪枝,设置一个函数check(i,j,k)判断从网格的下标[i][j]位置出发,能不能搜索到单词word[k]...word[wordSize-1](即word中下标k开始的后缀字符串)。判断所有的check(i,j,0),只要有一个为真即为真,否则为假。

对于check函数,如果board[i][j]!=word[k],return false;如果board[i][j]!=word[k]&&k==wordSize-1,return true;否则就判断相邻的四个位置能不能搜到word[k+1]...word[wordSize-1]。

要注意的是,check函数中包含了多次递归调用,如果是c++的话,参数写成传引用,这样比值传递运行速度快,能过。值传递的话我试过过不了。文章来源地址https://www.toymoban.com/news/detail-734407.html

i代码:

class Solution {
public:
    //往右,左,下,上四个方向走时行下标的变化和列下标的变化
    int directions[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
    bool check(vector<vector<char>> &board,int m,int n,vector<vector<int>> &visited,int i,int j,string word,int wordSize,int k)
    {
        if(board[i][j]!=word[k])
            return false;
        else if(k==wordSize-1)
            return true;
        visited[i][j]=1;
        for(int direc=0;direc<4;direc++)
        {//依次往四个方向走
            int newi=i+directions[direc][0],newj=j+directions[direc][1];
            if(newi>=0&&newi<m&&newj>=0&&newj<n&&visited[newi][newj]==0)
            {
                bool flag=check(board,m,n,visited,newi,newj,word,wordSize,k+1);
                if(flag)
                {
                    return true;
                }
            }
        }
        visited[i][j]=0;
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        int m=board.size();
        int n=board[0].size();
        vector<vector<int>> visited(m,vector<int>(n,0));
        int wordSize=word.size();
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                bool flag=check(board,m,n,visited,i,j,word,wordSize,0);
                if(flag)
                    return true;
            }
        }
        return false;
    }
};

到了这里,关于力扣每日一题79:单词搜索的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 剑指 Offer 12. 矩阵中的路径 / LeetCode 79. 单词搜索(深度优先搜索)

    链接:剑指 Offer 12. 矩阵中的路径;LeetCode 79. 单词搜索 难度:中等 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相

    2024年02月02日
    浏览(41)
  • 每日一题——LeetCode1455.检查单词是否为句中其他单词的前缀

    方法一 js函数slice()  将字符串按空格符分割为单词数组,记searchWord的长度为n,分割每个单词的前n位看是否和searchWord匹配 消耗时间和内存情况: 方法二 双指针: 来自leetcode官方题解 链接:1455.检查单词是否为句中其他单词的前缀 使用 start 记录单词的起始,end记录单词结尾

    2024年02月19日
    浏览(52)
  • 力扣79. 单词搜索

    思路: 定义函数 check(i,j,k) 为网格 (i,j) 位置出发能够搜索到单词 word(k),如果搜索到返回 true,否则返回 false; 搜索规则: 【R1】如果 board[i][j] != word[k],直接返回 false; 【R2】如果当前已经访问到字符串的末尾,且对应字符依然匹配,此时直接返回 true; 【R3】否则,遍历

    2024年01月18日
    浏览(39)
  • (搜索) 剑指 Offer 12. 矩阵中的路径 ——【Leetcode每日一题】

    难度:中等 给定一个 m * n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许

    2024年02月12日
    浏览(40)
  • (搜索) 剑指 Offer 38. 字符串的排列 ——【Leetcode每日一题】

    难度:中等 输入一个字符串,打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组,但里面 不能有重复元素 。 示例: 输入:s = “abc” 输出:[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”] 限制 : 1 = s 的长度 = 8 💡思路:回溯 可以直接 暴力穷举 ,但

    2024年02月12日
    浏览(49)
  • (搜索) 剑指 Offer 13. 机器人的运动范围 ——【Leetcode每日一题】

    难度:中等 地上有一个 m 行 n 列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于 k 的格子。例如,当 k 为18时,机器人能够进入方格

    2024年02月11日
    浏览(55)
  • 【LeetCode】每日一题&最后一个单词的长度&投票法求解多数元素&异或操作符巧解只出现一次的数字&整数反转

    ========================================================================= 个人主页直达: 小白不是程序媛 LeetCode系列专栏: LeetCode刷题掉发记 ========================================================================= 目录 LeetCode 58.最后一个单词的长度 LeetCode169.多数元素 LeetCode 136.出现一次的数字 LeetCode 7.整数

    2024年02月08日
    浏览(45)
  • ( “树” 之 BST) 109. 有序链表转换二叉搜索树 ——【Leetcode每日一题】

    二叉查找树(BST):根节点大于等于左子树所有节点,小于等于右子树所有节点。 二叉查找树中序遍历有序。 给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子

    2023年04月23日
    浏览(39)
  • 『力扣每日一题07』字符串最后一个单词的长度

    气死我啦,今天这道题花了快一个小时,我学完了答案的解法,放上去在线 OJ ,一直报错,找来找去都找不到自己错在哪,明明跟答案一模一样。后来还是学了另一种解法,才跑出来的(°̥̥̥̥̥̥̥̥o°̥̥̥̥̥̥̥̥)   后来我对比了两种写法,复盘了一下,应该是第一种解法

    2024年02月09日
    浏览(45)
  • 【LeetCode - 每日一题】449. 序列化和反序列化二叉搜索树(23.09.04)

    给定一棵二叉搜索树,实现序列化和反序列化; 注意 val 范围,因此 在序列化时需要插入分隔符分割每个节点的 val ; 要善于利用 二叉搜索树的特性(中序遍历 = 递增排序) ; 前序遍历 + 中序遍历 可以重构一棵树,又由于二叉搜索树自带中序遍历,因此在序列化时保存前

    2024年02月10日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包