每日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实现房屋租赁管理系统设计演示 摘要 互联网发展至今,无论是其理论还是技术都已经成熟,而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播,搭配信息管理工具可以很好地为人们提供服务。针对房屋租赁信息管理混乱&…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
基于Springboot+Vue的办公管理系统
角色: 管理员、员工 技术: 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能: 该办公管理系统是一个综合性的企业内部管理平台,旨在提升企业运营效率和员工管理水…...
