每天一道leetcode:127. 单词接龙(图论困难建图广度优先遍历)

今日份题目:

字典 wordList 中从单词 beginWordendWord转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk

  • 每一对相邻的单词只差一个字母。

  • 对于 1 <= i <= k 时,每个 si 都在 wordList 中。注意, beginWord 不需要在 wordList 中。

  • sk == endWord

给你两个单词 beginWordendWord 和一个字典 wordList ,返回 beginWordendWord最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0

示例1

输入:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出:5
解释:一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例2

输入:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出:0
解释:endWord "cog" 不在字典中,所以无法进行转换。

提示

  • 1 <= beginWord.length <= 10

  • endWord.length == beginWord.length

  • 1 <= wordList.length <= 5000

  • wordList[i].length == beginWord.length

  • beginWordendWordwordList[i] 由小写英文字母组成

  • beginWord != endWord

  • wordList 中的所有字符串 互不相同

题目思路

首先考虑建图,其次考虑遍历图。

我们把单词抽象成虚拟点,然后将单词拆分成只改变一个字母的虚拟节点。如:对于单词 hit,我们创建三个虚拟节点 * it、h * t、hi *,并让 hit 向这三个虚拟节点分别连一条边。如果一个单词能够转化为 hit,那么该单词必然会连接到这三个虚拟节点之一。对于每个单词,枚举它连接到的所有的虚拟节点,把该单词节点与这些虚拟节点相连即可。

最后进行广度优先遍历,当遍历到终点时,就找到了最短路径的长度。

注意:由于添加了虚拟节点,得到的距离为实际最短路径长度的两倍。同时由于并未计算起点的贡献,所以应当返回距离的一半再加一。

代码

class Solution 
{
public:unordered_map<string,int> dict; //存放字典内容vector<vector<int>> edge;int nodeNum=0; //用来标记是第几个点void wordNode(string& word) //把单词抽象为一个点{if(!dict.count(word)) //字典中没有这个点{dict[word]=nodeNum;nodeNum++;edge.emplace_back();}}void Edge(string& word) //如果两个单词可以通过只改变一个字母实现转换,表示两点之间有条边{wordNode(word); //建立点int u=dict[word]; //边的第一个端点for(char& c:word) //遍历所有位置,得到各虚拟节点*it、h*t、hi*{//hit<->*it,hit<->h*t,hit<->hi*char temp=c;c='*';wordNode(word); //分别建立虚拟点int v=dict[word]; //边的第二个端点//建立无向图的边edge[u].push_back(v);edge[v].push_back(u);c=temp; //恢复原单词}}int ladderLength(string beginWord, string endWord, vector<string>& wordList) {for(string& word:wordList) //对字典中的每个单词建立边{Edge(word);}Edge(beginWord); //对初始单词建立边if(!dict.count(endWord)) return 0; //无法变化为结果的样子//注意,由于是在建立边的过程中建立虚拟点,所以一定要先建好边再判断能否变化为结果单词vector<int> dis(nodeNum,INT_MAX); //记录变化步数int begin=dict[beginWord],end=dict[endWord]; //开始的点和结束的点dis[begin]=0;queue<int> p;p.push(begin);//bfswhile(!p.empty()) {int cur=p.front();p.pop();if(cur==end) {//因为添加了虚拟节点,所以得到的距离为实际最短路径长度的两倍;同时由于未计算起点的贡献,所以应当返回距离的一半再加一return dis[end]/2+1;}for(int& c:edge[cur]) //遍历当前单词可以进行的变化{//如果一个单词能够转化为 hit,那么该单词必然会连接到上述三个虚拟节点之一if(dis[c]==INT_MAX) //还没到过这个单词变化情况{dis[c]=dis[cur]+1; //这种情况是在原来情况下变一个字母,步数加一p.push(c);}}}return 0;}
};

提交结果

欢迎大家在评论区讨论,如有不懂的部分,欢迎在评论区留言!

更新不易,宝子们点个赞支持下,谢谢!

每天一道leetcode,大家一起在评论区打卡呀!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/99235.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

PSP - 开源可训练的蛋白质结构预测框架 OpenFold 的环境配置

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/132334671 Paper: OpenFold: Retraining AlphaFold2 yields new insights into its learning mechanisms and capacity for generalization Open…

在思科(Cisco)设备上配置 DHCP 服务器

DHCP广泛用于LAN环境中&#xff0c;从集中式服务器动态分配主机IP地址&#xff0c;从而显着减少IP地址管理的开销。DHCP 还有助于节省有限的 IP 地址空间&#xff0c;因为不再需要将 IP 地址永久分配给主机&#xff0c;只有连接到网络的主机才会使用 IP 地址。DHCP 服务器将路由…

“维度削减+逻辑回归”:如何使用PCA大幅提升乳腺癌的预测成功率?

一、引言 乳腺癌是女性中最常见的恶性肿瘤之一&#xff0c;也影响着全球范围内许多人们的健康。据世界卫生组织&#xff08;WHO&#xff09;的数据&#xff0c;乳腺癌是全球癌症发病率和死亡率最高的肿瘤之一&#xff0c;其对个体和社会的危害不可忽视。因此&#xff0c;早期乳…

ShowMeBug CEO李亚飞受邀参加深圳青年创新创业系列沙龙电子信息专场

7月13日下午&#xff0c;由深圳市科技交流服务中心&#xff08;深圳市科技专家委员会办公室&#xff09;主办&#xff0c;深圳新一代产业园承办的“2023深圳青年创新创业系列沙龙——电子信息专场”活动举行。ShowMeBug CEO李亚飞受邀参加此次活动。 深圳市科学技术协会党组成员…

pdf格式文件下载不预览,云存储的跨域解决

需求背景 后端接口中返回的是pdf文件路径比如&#xff1a; pdf文件路径 &#xff08;https://wangzhendongsky.oss-cn-beijing.aliyuncs.com/wzd-test.pdf&#xff09; 前端适配是这样的 <ahref"https://wangzhendongsky.oss-cn-beijing.aliyuncs.com/wzd-test.pdf&…

【仿写tomcat】二、扫描java文件,获取带有@WebServlet注解的类

tomcat仿写 项目结构扫描文件servlet注解map容器servlet工具类启动类调用 项目结构 扫描文件之前当然要确定一下项目结构了&#xff0c;我这里的方案是tomcat和项目同级 项目的话就仿照我们平时使用的结构就好了&#xff0c;我们规定所有的静态资源文件都在webApp目录下存放…

qiiuzhiji4

本篇是从慧与离职后到2023年8月21日这段时间的经历 2023/7/31至2023/8/21 本篇初次写于2023年8月21日 从慧与离职后基本上就是在专心找工作了&#xff0c;但是有在这段时间找工作经历的人都明白&#xff0c;IT行业不复以往了。尤其是对于我这样的普通二本学历的人来说&#xff…

Ubuntu系统下搭建QtCreator开发环境详细过程(Qt简介;Linux下安装QtCreator)

关于Qt的相关介绍&#xff0c;可以参考QT从入门到实战x篇&#xff0c;Qt 5.9 C开发指南&#xff0c;对于重复部分&#xff0c;本栏目不做详细介绍。关于Linux的基础&#xff0c;本人将重新整理一个栏目&#xff0c;就叫Linux基础吧&#xff0c;有需要的可以后期关注下。 文章目…

发布python模仿2023年全国职业的移动应用开发赛项样式开发的开源的新闻api,以及安卓接入案例代码

python模仿2023年全国职业的移动应用开发赛项样式开发的开源的新闻api&#xff0c;以及原生安卓接入案例代码案例 源码地址:keyxh/newsapi: python模仿2023年全国职业的移动应用开发赛项样式开发的开源的新闻api&#xff0c;以及安卓接入案例代码 (github.com) 目录 1.环境配…

Fast DDS (2)

1、结构&#xff1a; Fast DDS的架构如下图所示&#xff0c;可以看到以下不同环境的层模型&#xff1a; 应用层&#xff1a;利用Fast DDS API 在分布式系统中实现通信的用户应用程序。Fast DDS层&#xff1a;DDS 通信中间件的稳健实现。它允许部署一个或多个 DDS 域&#xff…

leetcode303. 区域和检索 - 数组不可变(java)

前缀和数组的应用 区域和检索 - 数组不可变题目描述前缀和数组代码演示 区域和检索 - 数组不可变 难度 - 简单 原题链接 - 区域和检索 - 数组不可变 题目描述 给定一个整数数组 nums&#xff0c;处理以下类型的多个查询: 计算索引 left 和 right &#xff08;包含 left 和 righ…

Python支持下最新Noah-MP陆面模式站点、区域模拟及可视化分析技术教程

详情点击公众号链接&#xff1a;Python支持下最新Noah-MP陆面模式站点、区域模拟及可视化分析技术教程 Noah-MP 5.0模型&模型所需环境的搭建 陆面过程的主要研究内容&#xff08;陆表能量平衡、水循环、碳循环等&#xff09;&#xff0c;陆面过程研究的重要性。 图 1 陆面…

MySQL语法及常用数据类型

一、SQL语言概述 对数据库进行查询和修改操作的语言叫做SQL。SQL的含义就是结构化查询语言&#xff08;Structured Query Language&#xff09;。SQL包含以下4个部分&#xff1a; 1、数据定义语言&#xff08;DDL&#xff09;&#xff1a;DROP、CREATE、ALTER等语句&#xff…

jenkins 日志输出显示时间戳的方式

网上很多方式比较片面&#xff0c;最新版插件直接使用即可无需更多操作。 使用方式如下&#xff1a; 1.安装插件 Timestamper 2.更新全局设置 系统设置-找到 Timestamper 勾选 Enabled for all Pipeline builds 也可修改时间戳格式。 帮助信息中显示 When checked, timesta…

ARM--day5(C语言点灯实验、总线、串口通信信息、串口通讯协议)

函数分装实现点灯 gpio.c: #include "gpio.h" //函数功能&#xff1a;GPIO引脚初始化操作 //参数1&#xff1a;GPIO组号 //参数2&#xff1a;引脚编号 //参数3&#xff1a;初始化内容 void hal_gpio_init(volatile gpio_t*gpiox,unsigned int pin,gpio_init_t* ini…

rabbitmq的死信队列

目录 成为死信的条件 消息TTL过期 队列达到最大长度 消息被拒 延迟队列 延迟队列使用场景 消息设置 TTL 队列设置 TTL 两者区别 producer 将消息投递到 broker 或者直接到 queue 里了&#xff0c; consumer 从 queue 取出消息 进行消费&#xff0c;但某些时候由…

最新Win10离线安装.NET Framework 3.5的方法(附离线包2022/3/22)

win10系统安装软件时&#xff0c;可能需要.net framework3.5的运行环境&#xff0c;当我们安装某些软件的时候会提示“你的电脑上的应用需要使用以下Windows功能:.NET Framework 3.5(包括.NET 2.0和3.0)。如果系统默认的是4.0以上的版本&#xff0c;当软件需要.net framework3.…

LVS+Keepalived集群

keepalived Keepalived及其工作原理 Keepalived 是一个基于VRRP协议来实现的LVS服务高可用方案&#xff0c;可以解决静态路由出现的单点故障问题 在一个LVS服务集群中通常有主服务器&#xff08;MASTER&#xff09;和备份服务器&#xff08;BACKUP&#xff09;两种角色的服务…

提升管班小诀窍

在传统教育中&#xff0c;将考试结果告知家长一直是一项相对麻烦的任务。老师们不得不一个一个的打电话或发短信&#xff0c;耗费大量时间和精力。然而&#xff0c;现在有了易查分&#xff0c;老师们可以轻松地创建自己的成绩查询系统&#xff0c;大大简化了这项任务。 好消息&…

【STM32】高效开发工具CubeMonitor快速上手

工欲善其事必先利其器。拥有一个辅助测试工具&#xff0c;能极大提高开发项目的效率。STM32CubeMonitor系列工具能够实时读取和呈现其变量&#xff0c;从而在运行时帮助微调和诊断STM32应用&#xff0c;类似于一个简单的示波器。它是一款基于流程的图形化编程工具&#xff0c;类…