leetcode 792_leetcode5421编码

leetcode 792_leetcode5421编码给定一个 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:输

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给定一个 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 仅由大小写英文字母组成

题解

  1. 深搜dfs
class Solution { 
   
public:
    typedef pair<int,int>PII;
    int dx[4] = { 
   0,1,0,-1},dy[4] = { 
   -1,0,1,0};
    bool dfs(PII p,int u,int len,vector<vector<char>> &board,string &word,vector<vector<bool> >&vis){ 
   
        if(u == len)return true;
        int x = p.first,y = p.second;
        if(x < 0 || x >= board.size() || y < 0 || y >= board[0].size())return false;
        if(vis[x][y])return false;
        vis[x][y] = true;
        if(board[p.first][p.second] == word[u]){ 
   
            for(int k = 0;k < 4;k ++){ 
   
                int a = p.first + dx[k],b = p.second + dy[k];
                if(dfs({ 
   a,b},u + 1,len,board,word,vis))return true;
            }
        }
        vis[p.first][p.second] = false;
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) { 
   
        int n = board.size(),m = board[0].size();
        vector<vector<bool> >vis(n,vector<bool>(m,false));
        for(int i = 0;i < n;i ++){ 
   
            for(int j = 0;j < m;j ++){ 
   
                if(dfs({ 
   i,j},0,word.size(),board,word,vis))return true;
            }
        }
        return false;
    }
};
  1. 宽搜bfs
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168872.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Java分页原理_分页系统原理

    Java分页原理_分页系统原理Java分页常见的分页实现方式使用List接口中的subList(intstartIndex,intendIndex)方法实现分页直接使用数据库SQL语句实现分页使用hibernate等框架实现跨数据库的分页使用subList()实现分页使用数据库SQL语句实现分页mysql数据库使用limit关键字,oracle中使用rownum关键字。例如,从学生表(

  • 【浅谈】日文的文本等出现乱码的情况以及解决办法「建议收藏」

    【浅谈】日文的文本等出现乱码的情况以及解决办法「建议收藏」参考链接Word里日文文档乱码问题ansi编码字符集和编码的区别.GB2312是一个字符集,那ANSI是编码,但是他俩是什么个意思?日文的文本出现乱码前言遇到了一个txt日文文本,出现大面积乱码。而且不懂日文,乱码的话,连翻译软件也无法使用。【上图为测试文本】以下的解释与解决办法为自己的想法等,并不一定准确。目录1.简单的解释2.如何解决3.附件一、简单的…

  • 借你一双慧眼,识别代码安全审计工具「建议收藏」

    借你一双慧眼,识别代码安全审计工具「建议收藏」代码安全审计产品、代码缺陷分析产品、代码安全分析等基于源代码静态分析技术的产品市场上越来越多,但是质量却层次不齐,误报率非常高,漏报率也不低,究其原因是为什么呢?因为一款静态分析类产品研发不是轻松的事,往往要经历几年时间,产品才会逐渐成熟,支持的开发语言和安全漏洞类型才能达到企业级应用水平,一般中小企业是很难投入如此长的时间进行研发的,而且静态分析类产品底…

  • 循环队列的实现

    循环队列的实现

  • checkbox选中与取消选择[通俗易懂]

    checkbox选中与取消选择[通俗易懂]checkbox选中与取消选择1.html&lt;form&gt;&lt;inputtype="checkbox"name="items"value="足球"/&gt;足球&lt;inputtype="checkbox"name="items"value="篮球"/&gt;篮球&

  • 【我的OpenGL学习进阶之旅】什么是TGA文件以及如何打开TGA文件?「建议收藏」

    什么是TGA文件?具有TGA文件扩展名的文件是Truevision图形适配器图像文件。它也很流行是Targa图形文件,TruevisionTGA或只是TARGA,这意味着Truevision高级栅格图形适配器。您可能会发现普通图像查看器无法打开TGA苍蝇。“Targa图形”格式的图像可能以原始格式或压缩格式存储,这对于图标,线条图和其他简单图像可能是首选。TGA格式通常与视频游戏中使用的图像文件有关。TGA文件可以是未压缩的原始文件,也可以是无损的RLE压缩文件。这种压缩方式对于图标和线条

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号