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

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&#xff1a; 每一对相邻的单词只差一个字母。 对于 1 < i < k 时&#xff…...

HTML DOM 事件监听器

通过JavaScript&#xff0c;我们可以给页面的某些元素添加事件的监听器&#xff0c;当元素触发相应事件的时候监听器就会捕捉到这个事件并执行相应的代码。addEventListener() 方法实例当用户点击按钮时触发监听事件&#xff1a;document.getElementById("myBtn").ad…...

java基本数据类型取值范围

在JAVA中一共有八种基本数据类型&#xff0c;他们分别是 byte、short、int、long、float、double、char、boolean 整型 其中byte、short、int、long都是表示整数的&#xff0c;只不过他们的取值范围不一样 byte的取值范围为-128~127&#xff0c;占用1个字节&#xff08;-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的含义以及设置导入函数的作用域

放丢失&#xff0c;转载一下&#xff0c;原文&#xff1a;https://blog.csdn.net/qq_31348733/article/details/1010546251. 上下文(context)的含义导入函数的上下文是该函数定义所在的位置&#xff0c;比如$unit 、模块、program或者package作用域(scope)&#xff0c;这一点跟…...

redis数据类型

Redis 数据类型 redis无论什么数据类型&#xff0c;在数据库中都是以key-value形式保存&#xff0c;并且所有的key(键)都是字符串&#xff0c;所以讨论基础数据结构都是讨论的value值的数据类型 1. 字符串操作 set key value [ex seconds] [px milliseconds] [nx|xx] 设置ke…...

【独家】华为OD机试 - 最多获得的短信条数(C 语言解题)

最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧文章目录 最近更新的博客使用说明本期…...

【剧前爆米花--爪哇岛寻宝】包装类的装拆箱和泛型的擦除机制

作者&#xff1a;困了电视剧 专栏&#xff1a;《数据结构--Java》 文章分布&#xff1a;这是关于数据结构的基础之一泛型的文章&#xff0c;希望对你有所帮助。 目录 包装类 装箱 装箱源码小细节 拆箱 泛型 什么是泛型 泛型编译的擦除机制 不能实例化泛型类型数组 包装…...

BufferQueue研究

我们在工作的过程中&#xff0c;肯定听过分析卡顿或者冻屏问题的时候&#xff0c;定位到APP卡在dequeueBuffer方法里面&#xff0c;或者也听身边的同事老说3Buffer等信息。所以3Buffer是什么鬼&#xff1f;什么是BufferQueue?搞Android&#xff0c;你一定知道Graphic Buffer和…...

【计组笔记08】计算机组成与原理之IO设备系统(输入、输出设备、外存储器)

这篇文章,主要介绍计算机组成与原理之IO设备系统(输入、输出设备、外存储器)。 目录 一、IO设备系统 1.1、IO系统的演变 (1)早期阶段 (2)接口模块和DMA阶段...

使用Vue实现数据可视化大屏功能(一)

导语   现在在很多的工程项目中&#xff0c;都有有关于数据大屏相关的监控内容&#xff0c;这里我们就来看一下如何用Vue来搭建一个数据可视化大屏应用。 创建项目 使用WebStorm工具创建一个Vue的项目。如下图所示&#xff0c;配置好vue的脚手架工具和nodejs的运行环境&#…...

华为OD机试真题Python实现【整数对最小和】真题+解题思路+代码(20222023)

整数对最小和 题目 给定两个整数数组 array1 array2 数组元素按升序排列 假设从array1 array2中分别取出一个元素可构成一对元素 现在需要取出K个元素 并对取出的所有元素求和 计算和的最小值 注意: 两对元素如果对应于array1 array2中的两个下标均相同,则视为同一个元素 �…...

2023年绿色建筑国际会议(ICoGB 2023)

2023年绿色建筑国际会议&#xff08;ICoGB 2023&#xff09; 重要信息 会议网址&#xff1a;www.icogb.org 会议时间&#xff1a;2023年5月19-21日 召开地点&#xff1a;斯德哥尔摩 截稿时间&#xff1a;2023年4月1日 录用通知&#xff1a;投稿后2周内 收录检索&#xff…...

【力扣1653】使字符串平衡的最少删除次数

给你一个字符串 s &#xff0c;它仅包含字符 a 和 b​​​​ 。你可以删除 s 中任意数目的字符&#xff0c;使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j &#xff0c;且 s[i] b 的同时 s[j] a &#xff0c;此时认为 s 是 平衡 的。请你返回使 s 平衡 的 最少 删除次数。…...

链表的中间结点与链表的倒数第k个结点(精美图示详解哦)

全文目录引言链表的中间结点题目描述与思路实现链表的倒数第k个结点题目描述与思路实现总结引言 在上一篇文章中&#xff0c;介绍了反转链表 我们利用了链表是逻辑连续的特点&#xff0c;逆置了链表的逻辑连接顺序&#xff0c;从而实现反转链表&#xff1a; 戳我查看反转链表详…...

防静电监控仪可以检测现场设备是否和实际大地接触

随着电子产品集成化度越来越高&#xff0c;对于电子产品装配来说&#xff0c;静电的危害严重影响到产品的质量、成品率和可靠性, 必须对用于电子产品装配的净化间进行系统防静电措施&#xff0c;将生产过程中的静电危害程度降至最低。近年来电子企业对ESD的危害的深入认识&…...

计算机网络第八版——第二章课后题答案(超详细)

第二章 该答案为博主在网络上整理&#xff0c;排版不易&#xff0c;希望大家多多点赞支持。后续将会持续更新&#xff08;可以给博主点个关注~ 第一章 答案 【2-01】物理层要解决哪些问题&#xff1f;物理层的主要特点是什么&#xff1f; 解答&#xff1a;物理层考虑的是怎…...

2023年3月全国DAMA-CDGA/CDGP数据管理认证火热报名中...

弘博创新是DAMA中国授权的数据治理人才培养基地&#xff0c;贴合市场需求定制教学体系&#xff0c;采用行业资深名师授课&#xff0c;理论与实践案例相结合&#xff0c;快速全面提升个人/企业数据治理专业知识与实践经验&#xff0c;通过考试还能获得数据专业领域证书。 DAMA认…...

查询与进程调度(CFS)相关信息

目录 查询与进程相关的调度信息 查看CFS调度信息 CPU相关的信息 CFS就绪队列的总运行时间 实时队列与deadline调度的相关信息 所有进程相关的信息 查询与进程相关的调度信息 进程的nice值&#xff0c;优先级&#xff0c;调度策略,vruntime等信息。在proc目录下&#xf…...

07对MVC的理解

MVC是一种设计模式&#xff0c;用于将应用程序的不同方面分离开来&#xff0c;以便更容易地管理和维护应用程序。MVC代表模型-视图-控制器&#xff0c;它将应用程序分为三个主要组件&#xff1a;模型&#xff08;Model&#xff09;&#xff1a;负责管理应用程序的数据和业务逻辑…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

C++--string的模拟实现

一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现&#xff0c;其目的是加强对string的底层了解&#xff0c;以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量&#xff0c;…...

【阅读笔记】MemOS: 大语言模型内存增强生成操作系统

核心速览 研究背景 ​​研究问题​​&#xff1a;这篇文章要解决的问题是当前大型语言模型&#xff08;LLMs&#xff09;在处理内存方面的局限性。LLMs虽然在语言感知和生成方面表现出色&#xff0c;但缺乏统一的、结构化的内存架构。现有的方法如检索增强生成&#xff08;RA…...

高保真组件库:开关

一:制作关状态 拖入一个矩形作为关闭的底色:44 x 22,填充灰色CCCCCC,圆角23,边框宽度0,文本为”关“,右对齐,边距2,2,6,2,文本颜色白色FFFFFF。 拖拽一个椭圆,尺寸18 x 18,边框为0。3. 全选转为动态面板状态1命名为”关“。 二:制作开状态 复制关状态并命名为”开…...

运行vue项目报错 errors and 0 warnings potentially fixable with the `--fix` option.

报错 找到package.json文件 找到这个修改成 "lint": "eslint --fix --ext .js,.vue src" 为elsint有配置结尾换行符&#xff0c;最后运行&#xff1a;npm run lint --fix...

多模态大语言模型arxiv论文略读(110)

CoVLA: Comprehensive Vision-Language-Action Dataset for Autonomous Driving ➡️ 论文标题&#xff1a;CoVLA: Comprehensive Vision-Language-Action Dataset for Autonomous Driving ➡️ 论文作者&#xff1a;Hidehisa Arai, Keita Miwa, Kento Sasaki, Yu Yamaguchi, …...