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)
blank

相关推荐

  • Redis的那些最常见面试问题

    Redis的那些最常见面试问题

  • linux修改用户密码命令_linux更改用户密码的命令

    linux修改用户密码命令_linux更改用户密码的命令Linux修改用户密码使用的Linux版本是:ubuntu-18.10-live-server-amd64知道一个用户名密码时,修改用户密码,各个版本下都是通用的;重置密码的时候,版本不同,可能操作的地方不一样了。如果一个账号的密码都不记得了(这通常是需要修改用户密码最多的情况),那就需要重置密码,相对就比较复杂一些,放在最后讲。但凡知道一个用户的密码,那就好办。(普通用户登录的情况下,也可以修改root用户的密码。)1.知道一个账号的密码这就是正常情况下,修改用户密码。1.1知道roo

  • 了解automake和autoconf(autoreconf)[通俗易懂]

    了解automake和autoconf(autoreconf)[通俗易懂]本文转载自《例解autoconf和automake生成Makefile文件》 通过这篇文章可以了解auotmake和autoconf的基本工作流程,文章讲的通俗易懂,但是版本较老。了解新版本的automake可以参考automake的WiKi主页Automake,通过下图可以很清晰的了解auomake和autoconf是如何生成configure脚本文件和最终的makefile文件…

    2022年10月31日
  • DP算法分类总结_算法总结

    DP算法分类总结_算法总结转载请注明出处,谢谢。&nbsp;&nbsp;http://blog.csdn.net/cc_again?viewmode=list&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;———-&nbsp;Accagain&nbsp;…

    2022年10月21日
  • Android工具类整合「建议收藏」

    Android工具类整合「建议收藏」Android-JSONUtil工具类常用的Json工具类,包含Json转换成实体、实体转json字符串、list集合转换成json、数组转换成jsonpublicclassJSONUtil{privatestaticfinalStringTAG=JSONUtil.class.getSimpleName();privateJSONUtil()…

  • ELK日志原理与介绍

    ELK日志原理与介绍ELK日志原理与介绍

发表回复

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

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