Java——单词接龙
题目链接
leetcode在线oj题——单词接龙
题目描述
字典 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
- beginWord、endWord 和 wordList[i] 由小写英文字母组成
- beginWord != endWord
- wordList 中的所有字符串 互不相同
解题思路
使用广度优先搜索
将字符串的所有字符都替换成其他的25个字符,查看wordList中是否有该单词,如果有就将该单词加入到队列中,最后再弹出该元素
例如:先将beginword加入到队列中

对hit的每一位的字符都进行遍历,将其变成其他的25个字母,例如先是hit的’h’,变成ait,发现ait并不在wordList中,继续变成bit…
第一个字符变换了25个字符都没有wordList中的字符串与之匹配
继续变换第二个字符‘i’,先是变成hat,然后是hbt…
一直将所有字符都替换查看是否匹配,如果匹配就将其放到队列里
最后只有将第二个字符变成o才有hot与之匹配,这时将hot放入队列,step++,将队列中的hit取出

然后继续将队列中的所有元素都拿出来,分别变换字符查看是否有匹配的,如果有并且没有遍历过,就放入队列中

继续重复上面的操作

继续重复

最终找到单词cog,返回step = 5
代码
class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {int step = 1;Queue<String> queue = new LinkedList<>();HashSet<String> isUsed = new HashSet<>();HashSet<String> dict = new HashSet<>();//添加第一个单词queue.offer(beginWord);isUsed.add(beginWord);//将链表转换为哈希表for (int i = 0; i < wordList.size(); i++) {dict.add(wordList.get(i));}while(!queue.isEmpty()){int size = queue.size();while(size != 0){String curString = queue.poll();if(curString.equals(endWord)){return step;}//修改单词中的一个字符for (int i = 0; i < curString.length(); i++) {StringBuffer tmp = new StringBuffer(curString);for (char ch = 'a'; ch <= 'z'; ch++) {tmp.setCharAt(i,ch);String newString = tmp.toString();//判断新的单词是否在词典中,并且没有搜索过if(!isUsed.contains(newString) && dict.contains(newString)){queue.offer(newString);isUsed.add(newString);}}}size--;}step++;}return 0;}
}
相关文章:
Java——单词接龙
题目链接 leetcode在线oj题——单词接龙 题目描述 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk: 每一对相邻的单词只差一个字母。 对于 1 < i < k 时ÿ…...
HTML DOM 事件监听器
通过JavaScript,我们可以给页面的某些元素添加事件的监听器,当元素触发相应事件的时候监听器就会捕捉到这个事件并执行相应的代码。addEventListener() 方法实例当用户点击按钮时触发监听事件:document.getElementById("myBtn").ad…...
java基本数据类型取值范围
在JAVA中一共有八种基本数据类型,他们分别是 byte、short、int、long、float、double、char、boolean 整型 其中byte、short、int、long都是表示整数的,只不过他们的取值范围不一样 byte的取值范围为-128~127,占用1个字节(-2的…...
maven的安装配置
目录 1. Maven的安装配置 1.1检测jdk的版本 1.2下载maven 1.3配置maven环境变量 2.认识maven的目录结构 2.1 创建一个文件夹作为项目的根目录 1.创建如下结构的目录 2. 在pom.xml文件中写入如下内容(不用记忆) 3.在mian-->java--》下边创建java文件编辑 4.cmd下…...
【转载】System Verilog 上下文context的含义以及设置导入函数的作用域
放丢失,转载一下,原文:https://blog.csdn.net/qq_31348733/article/details/1010546251. 上下文(context)的含义导入函数的上下文是该函数定义所在的位置,比如$unit 、模块、program或者package作用域(scope),这一点跟…...
redis数据类型
Redis 数据类型 redis无论什么数据类型,在数据库中都是以key-value形式保存,并且所有的key(键)都是字符串,所以讨论基础数据结构都是讨论的value值的数据类型 1. 字符串操作 set key value [ex seconds] [px milliseconds] [nx|xx] 设置ke…...
【独家】华为OD机试 - 最多获得的短信条数(C 语言解题)
最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧文章目录 最近更新的博客使用说明本期…...
【剧前爆米花--爪哇岛寻宝】包装类的装拆箱和泛型的擦除机制
作者:困了电视剧 专栏:《数据结构--Java》 文章分布:这是关于数据结构的基础之一泛型的文章,希望对你有所帮助。 目录 包装类 装箱 装箱源码小细节 拆箱 泛型 什么是泛型 泛型编译的擦除机制 不能实例化泛型类型数组 包装…...
BufferQueue研究
我们在工作的过程中,肯定听过分析卡顿或者冻屏问题的时候,定位到APP卡在dequeueBuffer方法里面,或者也听身边的同事老说3Buffer等信息。所以3Buffer是什么鬼?什么是BufferQueue?搞Android,你一定知道Graphic Buffer和…...
【计组笔记08】计算机组成与原理之IO设备系统(输入、输出设备、外存储器)
这篇文章,主要介绍计算机组成与原理之IO设备系统(输入、输出设备、外存储器)。 目录 一、IO设备系统 1.1、IO系统的演变 (1)早期阶段 (2)接口模块和DMA阶段...
使用Vue实现数据可视化大屏功能(一)
导语 现在在很多的工程项目中,都有有关于数据大屏相关的监控内容,这里我们就来看一下如何用Vue来搭建一个数据可视化大屏应用。 创建项目 使用WebStorm工具创建一个Vue的项目。如下图所示,配置好vue的脚手架工具和nodejs的运行环境&#…...
华为OD机试真题Python实现【整数对最小和】真题+解题思路+代码(20222023)
整数对最小和 题目 给定两个整数数组 array1 array2 数组元素按升序排列 假设从array1 array2中分别取出一个元素可构成一对元素 现在需要取出K个元素 并对取出的所有元素求和 计算和的最小值 注意: 两对元素如果对应于array1 array2中的两个下标均相同,则视为同一个元素 �…...
2023年绿色建筑国际会议(ICoGB 2023)
2023年绿色建筑国际会议(ICoGB 2023) 重要信息 会议网址:www.icogb.org 会议时间:2023年5月19-21日 召开地点:斯德哥尔摩 截稿时间:2023年4月1日 录用通知:投稿后2周内 收录检索ÿ…...
【力扣1653】使字符串平衡的最少删除次数
给你一个字符串 s ,它仅包含字符 a 和 b 。你可以删除 s 中任意数目的字符,使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j ,且 s[i] b 的同时 s[j] a ,此时认为 s 是 平衡 的。请你返回使 s 平衡 的 最少 删除次数。…...
链表的中间结点与链表的倒数第k个结点(精美图示详解哦)
全文目录引言链表的中间结点题目描述与思路实现链表的倒数第k个结点题目描述与思路实现总结引言 在上一篇文章中,介绍了反转链表 我们利用了链表是逻辑连续的特点,逆置了链表的逻辑连接顺序,从而实现反转链表: 戳我查看反转链表详…...
防静电监控仪可以检测现场设备是否和实际大地接触
随着电子产品集成化度越来越高,对于电子产品装配来说,静电的危害严重影响到产品的质量、成品率和可靠性, 必须对用于电子产品装配的净化间进行系统防静电措施,将生产过程中的静电危害程度降至最低。近年来电子企业对ESD的危害的深入认识&…...
计算机网络第八版——第二章课后题答案(超详细)
第二章 该答案为博主在网络上整理,排版不易,希望大家多多点赞支持。后续将会持续更新(可以给博主点个关注~ 第一章 答案 【2-01】物理层要解决哪些问题?物理层的主要特点是什么? 解答:物理层考虑的是怎…...
2023年3月全国DAMA-CDGA/CDGP数据管理认证火热报名中...
弘博创新是DAMA中国授权的数据治理人才培养基地,贴合市场需求定制教学体系,采用行业资深名师授课,理论与实践案例相结合,快速全面提升个人/企业数据治理专业知识与实践经验,通过考试还能获得数据专业领域证书。 DAMA认…...
查询与进程调度(CFS)相关信息
目录 查询与进程相关的调度信息 查看CFS调度信息 CPU相关的信息 CFS就绪队列的总运行时间 实时队列与deadline调度的相关信息 所有进程相关的信息 查询与进程相关的调度信息 进程的nice值,优先级,调度策略,vruntime等信息。在proc目录下…...
07对MVC的理解
MVC是一种设计模式,用于将应用程序的不同方面分离开来,以便更容易地管理和维护应用程序。MVC代表模型-视图-控制器,它将应用程序分为三个主要组件:模型(Model):负责管理应用程序的数据和业务逻辑…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
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 …...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...
Leetcode33( 搜索旋转排序数组)
题目表述 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...
