当前位置: 首页 > 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;搭配信息管理工具可以很好地为人们提供服务。针对房屋租赁信息管理混乱&…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

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…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

2025年- H71-Lc179--39.组合总和(回溯,组合)--Java版

1.题目描述 2.思路 当前的元素可以重复使用。 &#xff08;1&#xff09;确定回溯算法函数的参数和返回值&#xff08;一般是void类型&#xff09; &#xff08;2&#xff09;因为是用递归实现的&#xff0c;所以我们要确定终止条件 &#xff08;3&#xff09;单层搜索逻辑 二…...

【工具教程】多个条形码识别用条码内容对图片重命名,批量PDF条形码识别后用条码内容批量改名,使用教程及注意事项

一、条形码识别改名使用教程 打开软件并选择处理模式&#xff1a;打开软件后&#xff0c;根据要处理的文件类型&#xff0c;选择 “图片识别模式” 或 “PDF 识别模式”。如果是处理包含条形码的 PDF 文件&#xff0c;就选择 “PDF 识别模式”&#xff1b;若是处理图片文件&…...