每日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 <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord、endWord和wordList[i]由小写英文字母组成beginWord != endWordwordList中的所有字符串 互不相同
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: 每一对相邻的单词只差一个字母。…...
微信小程序英文版:实现一键切换中英双语版(已组件化)
已经重新优化代码做成了组件,需要可自取:https://github.com/CrystalCAI11/wechat-language-compoment 所有操作都打包在组件里不需要在额外的地方添加代码,直接在你需要的页面里导入组件,再在对应页面的onLoad()里set文本就行了。…...
openstack之neutron介绍
核心组件 neutron-server:提供API接口,把对应的api请求传给plugin进; neutron-plugin:管理逻辑网络状态,调用agent; neutron-agent:在provider network上创建网络对象; 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中子传父的方式及原理
方式挺多的,先说最常用的通过props进行父子组件的数据传递和修改以及原理 在React中,props不仅用于传递数据,它们也可以传递可以执行的函数,这使得子组件能够间接更新父组件的状态。这种方法强化了React的单向数据流策略…...
【数据结构与算法】贪心算法及例题
目录 贪心算法例题一:找零问题例题二:走廊搬运物品最优方案问题输入样例例题三:贪心自助餐 贪心算法 贪心算法是一种在每一步选择中都采取当前状态下最优的选择,以期望最终达到全局最优解的算法。它的核心思想是每次都选择当前最…...
【Origin+Python】使用External Python批量出图代码参考
目录 基本介绍环境配置官方代码示例基础代码详解我的代码效果视频进阶代码及去水印 基本介绍 origin2021后可以使用python实现批量绘图,一共有两种方式:一种是嵌入式Python,一种是外部Python访问Origin。详细介绍可以自己去查看,打…...
YOLOv8最新改进系列:融合DySample超轻量动态上采样算子,低延迟、高性能,目前最新上采样方法!!!遥遥领先!
YOLOv8最新改进系列:融合DySample超轻量动态上采样算子,低延迟、高性能,目前最新上采样方法!!!遥遥领先! DySample超轻量动态上采样算子全文戳这!here! 详细的改进教程以及源码&am…...
ChatGPT基础(二) ChatGPT的使用和调优
文章目录 ChatGPT的特性采用关键词进行提问给ChatGPT指定身份提升问答质量的策略1.表述方式上的优化2.用"继续"输出长内容3.营造场景4.由浅入深,提升问题质量5.预设回答框架和风格 ChatGPT的特性 1.能够联系上下文进行回答 ChatGPT回答问题是有上下文的&…...
麒麟 V10 离线 安装 k8s 和kuboard
目录 安装文件准备 主机准备 主机配置 修改主机名(三个节点分别执行) 配置hosts(所有节点) 关闭防火墙、selinux、swap、dnsmasq(所有节点) 安装依赖包(所有节点) 系统参数设置(所有节点) 时间同步…...
PlayerSettings.WebGL.emscriptenArgs设置无效的问题
1)PlayerSettings.WebGL.emscriptenArgs设置无效的问题 2)多个小资源包合并为大资源包的疑问 3)AssetBundle在移动设备上丢失 4)Unity云渲染插件RenderStreaming,如何实现多用户分别有独立的操作 这是第381篇UWA技术知…...
项目管理工具——使用甘特图制定项目计划的详细步骤
甘特图是一种直观的项目管理工具,它有助于我们清晰地展示任务安排、时间管理和项目的进度。以下是使用甘特图制定项目计划的详细步骤: 1、创建项目:首先,在进度猫中创建新的项目,并设置项目的时间、工作日等参数。根据…...
python读取文件数据写入到数据库中,并反向从数据库读取保存到本地
学python,操作数据库是必不可少的,不光要会写python代码,还要会写SQL语句,本篇文章主要讲如何把本地txt文件中的数据读取出来并写入到对应的数据库中,同时将数据库单个表中的数据读出来保存在本地txt文件中。 话不多说…...
社交媒体数据恢复:Viber
Viber是一款流行的即时通讯应用,用于发送消息、语音通话和视频通话。然而,有时候我们会不小心删除一些重要的Viber聊天记录,这时候就需要进行数据恢复。本文将介绍如何在安卓设备上进行Viber数据恢复。 一、使用安卓数据恢复软件 安卓数据恢…...
蓝桥杯赛事介绍
蓝桥杯是由工业和信息化部人才交流中心主办的全国性IT学科赛事,全称为“蓝桥杯全国软件和信息技术专业人才大赛”。该赛事旨在推动软件和信息领域专业技术人才培养,提升大学生的创新能力和就业竞争力,为行业输送具有创新能力和实践能力的高端…...
TypeScript系列之-深度理解基本类型画图讲解
JS的类型(8): null undefined string number boolean bigint symbol object(含 Array, Function,Date.....) TS的类型(87): 以上所有,加上 void, never, enum, unknown, any 再加上自定义类型 type interface 上一节我们说…...
Debian
使用root用户操作 直接使用su命令进行切换。 配置用户使用sudo命令 在安装好系统之后,使用用户名登录之后。需要执行需要root权限的命令,会发现无法执行成功。原因是没有配置用户使用sudo的权限。 编辑bash /etc/sudoers文件 可以先切换root用户安装…...
怎么使用JMeter进行性能测试?
一、简介 JMeter是Apache软件基金会下的一款开源的性能测试工具,完全由Java开发。它专注于对我们应用程序进行负载测试和性能测量,最初设计用于web应用程序,现在已经扩展到其他测试功能,比如:FTP、Database和LDAP等。…...
MySQL:锁的分类
文章目录 行级锁Record LockGap LockNext-Key Lock插入意向锁 表级锁表锁元数据锁(MDL)意向锁AUTO-INC 锁 全局锁 行级锁 Record Lock 记录锁有S锁(共享锁/读锁)和X锁(排他锁/写锁)之分,加完S…...
基于springboot实现房屋租赁管理系统设计项目【项目源码+论文说明】
基于springboot实现房屋租赁管理系统设计演示 摘要 互联网发展至今,无论是其理论还是技术都已经成熟,而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播,搭配信息管理工具可以很好地为人们提供服务。针对房屋租赁信息管理混乱&…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果