当前位置: 首页 > news >正文

每日OJ题_BFS解决最短路③_力扣127. 单词接龙

目录

③力扣127. 单词接龙

解析代码


③力扣127. 单词接龙

127. 单词接龙

难度 困难

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

  • 每一对相邻的单词只差一个字母。
  •  对于 1 <= i <= k 时,每个 si 都在 wordList 中。注意, beginWord 不需要在 wordList 中。
  • sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ,返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 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
  • beginWordendWord 和 wordList[i] 由小写英文字母组成
  • beginWord != endWord
  • wordList 中的所有字符串 互不相同
class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {}
};

解析代码

        和力扣433. 最小基因变化一样,如果将每次字符串的变换抽象成图中的两个顶点和一条边的话,问题就变成了边权为 1 的最短路问题。 因此,从起始的字符串开始,来一次 bfs 即可。

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> wordListHash(wordList.begin(), wordList.end());unordered_set<string> vis;if(!wordListHash.count(endWord))return 0;int ret = 1;queue<string> q;q.push(beginWord);vis.insert(beginWord);while(!q.empty()){++ret;int size = q.size();while(size--){string t = q.front();q.pop();for(int i = 0; i < t.size(); ++i){for(char ch = 'a'; ch <= 'z'; ++ch){string tmp = t;tmp[i] = ch;if(wordListHash.count(tmp) && !vis.count(tmp)){if(tmp == endWord)return ret;q.push(tmp);vis.insert(tmp);}}}}}return 0;}
};

相关文章:

每日OJ题_BFS解决最短路③_力扣127. 单词接龙

目录 ③力扣127. 单词接龙 解析代码 ③力扣127. 单词接龙 127. 单词接龙 难度 困难 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk&#xff1a; 每一对相邻的单词只差一个字母。…...

微信小程序英文版:实现一键切换中英双语版(已组件化)

已经重新优化代码做成了组件&#xff0c;需要可自取&#xff1a;https://github.com/CrystalCAI11/wechat-language-compoment 所有操作都打包在组件里不需要在额外的地方添加代码&#xff0c;直接在你需要的页面里导入组件&#xff0c;再在对应页面的onLoad()里set文本就行了。…...

openstack之neutron介绍

核心组件 neutron-server&#xff1a;提供API接口&#xff0c;把对应的api请求传给plugin进&#xff1b; neutron-plugin&#xff1a;管理逻辑网络状态&#xff0c;调用agent&#xff1b; neutron-agent&#xff1a;在provider network上创建网络对象&#xff1b; neutron-…...

学习Rust的第三天:猜谜游戏

基于Steve Klabnik的《The Rust Programming Language》一书。今天我们在rust中建立一个猜谜游戏。 Introduction 介绍 We will build a game that will pick a random number between 1 to 100 and the user has to guess the number on a correct guess the user wins. 我们将…...

React中子传父的方式及原理

方式挺多的&#xff0c;先说最常用的通过props进行父子组件的数据传递和修改以及原理 在React中&#xff0c;props不仅用于传递数据&#xff0c;它们也可以传递可以执行的函数&#xff0c;这使得子组件能够间接更新父组件的状态。这种方法强化了React的单向数据流策略&#xf…...

【数据结构与算法】贪心算法及例题

目录 贪心算法例题一&#xff1a;找零问题例题二&#xff1a;走廊搬运物品最优方案问题输入样例例题三&#xff1a;贪心自助餐 贪心算法 贪心算法是一种在每一步选择中都采取当前状态下最优的选择&#xff0c;以期望最终达到全局最优解的算法。它的核心思想是每次都选择当前最…...

【Origin+Python】使用External Python批量出图代码参考

目录 基本介绍环境配置官方代码示例基础代码详解我的代码效果视频进阶代码及去水印 基本介绍 origin2021后可以使用python实现批量绘图&#xff0c;一共有两种方式&#xff1a;一种是嵌入式Python&#xff0c;一种是外部Python访问Origin。详细介绍可以自己去查看&#xff0c;打…...

YOLOv8最新改进系列:融合DySample超轻量动态上采样算子,低延迟、高性能,目前最新上采样方法!!!遥遥领先!

YOLOv8最新改进系列&#xff1a;融合DySample超轻量动态上采样算子&#xff0c;低延迟、高性能&#xff0c;目前最新上采样方法&#xff01;&#xff01;&#xff01;遥遥领先&#xff01; DySample超轻量动态上采样算子全文戳这&#xff01;here! 详细的改进教程以及源码&am…...

ChatGPT基础(二) ChatGPT的使用和调优

文章目录 ChatGPT的特性采用关键词进行提问给ChatGPT指定身份提升问答质量的策略1.表述方式上的优化2.用"继续"输出长内容3.营造场景4.由浅入深&#xff0c;提升问题质量5.预设回答框架和风格 ChatGPT的特性 1.能够联系上下文进行回答 ChatGPT回答问题是有上下文的&…...

麒麟 V10 离线 安装 k8s 和kuboard

目录 安装文件准备 主机准备 主机配置 修改主机名&#xff08;三个节点分别执行&#xff09; 配置hosts&#xff08;所有节点&#xff09; 关闭防火墙、selinux、swap、dnsmasq(所有节点) 安装依赖包&#xff08;所有节点&#xff09; 系统参数设置(所有节点) 时间同步…...

PlayerSettings.WebGL.emscriptenArgs设置无效的问题

1&#xff09;PlayerSettings.WebGL.emscriptenArgs设置无效的问题 2&#xff09;多个小资源包合并为大资源包的疑问 3&#xff09;AssetBundle在移动设备上丢失 4&#xff09;Unity云渲染插件RenderStreaming&#xff0c;如何实现多用户分别有独立的操作 这是第381篇UWA技术知…...

项目管理工具——使用甘特图制定项目计划的详细步骤

甘特图是一种直观的项目管理工具&#xff0c;它有助于我们清晰地展示任务安排、时间管理和项目的进度。以下是使用甘特图制定项目计划的详细步骤&#xff1a; 1、创建项目&#xff1a;首先&#xff0c;在进度猫中创建新的项目&#xff0c;并设置项目的时间、工作日等参数。根据…...

python读取文件数据写入到数据库中,并反向从数据库读取保存到本地

学python&#xff0c;操作数据库是必不可少的&#xff0c;不光要会写python代码&#xff0c;还要会写SQL语句&#xff0c;本篇文章主要讲如何把本地txt文件中的数据读取出来并写入到对应的数据库中&#xff0c;同时将数据库单个表中的数据读出来保存在本地txt文件中。 话不多说…...

社交媒体数据恢复:Viber

Viber是一款流行的即时通讯应用&#xff0c;用于发送消息、语音通话和视频通话。然而&#xff0c;有时候我们会不小心删除一些重要的Viber聊天记录&#xff0c;这时候就需要进行数据恢复。本文将介绍如何在安卓设备上进行Viber数据恢复。 一、使用安卓数据恢复软件 安卓数据恢…...

蓝桥杯赛事介绍

蓝桥杯是由工业和信息化部人才交流中心主办的全国性IT学科赛事&#xff0c;全称为“蓝桥杯全国软件和信息技术专业人才大赛”。该赛事旨在推动软件和信息领域专业技术人才培养&#xff0c;提升大学生的创新能力和就业竞争力&#xff0c;为行业输送具有创新能力和实践能力的高端…...

TypeScript系列之-深度理解基本类型画图讲解

JS的类型(8)&#xff1a; null undefined string number boolean bigint symbol object&#xff08;含 Array, Function,Date.....&#xff09; TS的类型(87): 以上所有&#xff0c;加上 void, never, enum, unknown, any 再加上自定义类型 type interface 上一节我们说…...

Debian

使用root用户操作 直接使用su命令进行切换。 配置用户使用sudo命令 在安装好系统之后&#xff0c;使用用户名登录之后。需要执行需要root权限的命令&#xff0c;会发现无法执行成功。原因是没有配置用户使用sudo的权限。 编辑bash /etc/sudoers文件 可以先切换root用户安装…...

怎么使用JMeter进行性能测试?

一、简介 JMeter是Apache软件基金会下的一款开源的性能测试工具&#xff0c;完全由Java开发。它专注于对我们应用程序进行负载测试和性能测量&#xff0c;最初设计用于web应用程序&#xff0c;现在已经扩展到其他测试功能&#xff0c;比如&#xff1a;FTP、Database和LDAP等。…...

MySQL:锁的分类

文章目录 行级锁Record LockGap LockNext-Key Lock插入意向锁 表级锁表锁元数据锁&#xff08;MDL&#xff09;意向锁AUTO-INC 锁 全局锁 行级锁 Record Lock 记录锁有S锁&#xff08;共享锁/读锁&#xff09;和X锁&#xff08;排他锁/写锁&#xff09;之分&#xff0c;加完S…...

基于springboot实现房屋租赁管理系统设计项目【项目源码+论文说明】

基于springboot实现房屋租赁管理系统设计演示 摘要 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播&#xff0c;搭配信息管理工具可以很好地为人们提供服务。针对房屋租赁信息管理混乱&…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...