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

leetcode127单词接龙刷题打卡

127. 单词接龙

字典 wordList 中从单词 beginWordendWord转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk

  • 每一对相邻的单词只差一个字母。
  • 对于 1 <= i <= k 时,每个 si 都在 wordList 中。注意, beginWord 不需要在 wordList 中。
  • sk == endWord

给你两个单词 beginWordendWord 和一个字典 wordList ,返回 beginWordendWord最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 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
  • beginWordendWordwordList[i] 由小写英文字母组成
  • beginWord != endWord
  • wordList 中的所有字符串 互不相同

题解思路

在学习图论的时候做的一道题,完全没有思路,之前做的题都是二维矩阵,有个图样,轮到每个点有四个方向供我选择,这道题只有一个单词列表。

待解决问题:

  • 深搜or广搜

  • 如何建图

广搜

这道题应该用广度搜索,题目中要求最短路径,用广搜的话如果遍历到了则就是那么对应的路径就是最短路径

关于建图

之前是有一个图,然后我们遍历到每一个点后尝试该点的四个方向,

这道题没有图我们遍历到一个单词后该如何尝试方向呢?

题目要求每次只改变一个单词的一个字母且改变后的单词需要出现在wordlist中,我们就可以基于改变一个字母来确定遍历的方向

遍历方向为:

到每一个单词时,有word_length*26个方向供我们遍历

while(!que.empty()){string word = que.front(); que.pop();int path = visited[word]; // unordered_mapfor(int i = 0; i < word.size(); i++){string newWord = word;for(int j = 0; j < 26; j++){newWord[i] = j + 'a';// 入队处理 and 终止条件处理}}
}

我们对比一些二维矩阵的广搜核心框架

while(!que.empty()){pair<int, int> cur = que.front(); que.pop();int curx = cur.first;int cury = cur.second;for(int i = 0; i < 4; i++){int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];// 入队处理 and 终止条件处理}
}

通过广搜框架我们不需要显示的建图就可以像图一样搜索。

完整代码

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> wordSet(wordList.begin(), wordList.end());if(wordSet.find(endWord) == wordSet.end()) return 0;unordered_map<string, int> visited;visited[beginWord] = 1;queue<string> que;que.push(beginWord);while(!que.empty()){string word = que.front(); que.pop();int path = visited[word];for(int i = 0; i < word.size(); i++){string newWord = word;for(int j = 0; j < 26; j++){newWord[i] = j + 'a';if(newWord == endWord) return path + 1;if(wordSet.find(newWord) != wordSet.end() && visited.find(newWord)  == visited.end()){visited[newWord] = path + 1;que.push(newWord);}}}}return 0;}
};

相关文章:

leetcode127单词接龙刷题打卡

127. 单词接龙 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk&#xff1a; 每一对相邻的单词只差一个字母。对于 1 < i < k 时&#xff0c;每个 si 都在 wordList 中。注意&am…...

基于SSM的物流管理系统

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;采用JSP技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#x…...

EagleSDR USB HAT FT600

给EagleSDR做了个USB 3.0的子卡&#xff0c;采用FT600方案&#xff0c;实物如下&#xff1a; 用FT600DataStreamerDemoApp测试&#xff0c;速度如下&#xff1a; 由于FT600是16bit的接口&#xff0c;如果用FT601的32bit接口&#xff0c;性能应该还会有大幅提升。 测试代码很简…...

Java多线程(四)锁策略(CAS,死锁)和多线程对集合类的使用

锁策略&#xff08;CAS&#xff0c;死锁&#xff09;和多线程对集合类的使用 锁策略 1.乐观锁VS悲观锁 2.轻量级锁VS重量级锁 3.自旋锁VS挂起等待锁 4.互斥锁VS读写锁 5.可重入锁vs不可重入锁 死锁的第一种情况 死锁的第二种情况 死锁的第三种情况 CAS 1.实现原子类 …...

基于spring boot+ vue+ mysql开发的UWB室内外定位系统源码

现代制造业厂区面积大、人员数量多、物资设备不断增加&#xff0c;随着工业信息化技术的发展&#xff0c;大型制造企业中对人员、车辆、物资的管理要求越来越细致。 高精度定位管理系统使用UWB室内定位技术&#xff0c;通过在厂区安装定位基站&#xff0c;为人员或设备佩戴定位…...

第2章_瑞萨MCU零基础入门系列教程之面向过程与面向对象

本教程基于韦东山百问网出的 DShanMCU-RA6M5开发板 进行编写&#xff0c;需要的同学可以在这里获取&#xff1a; https://item.taobao.com/item.htm?id728461040949 配套资料获取&#xff1a;https://renesas-docs.100ask.net 瑞萨MCU零基础入门系列教程汇总&#xff1a; ht…...

数字图像处理:亮度对比度-几何变换-噪声处理

文章目录 数字图像增强亮度与对比度转换几何变换图像裁剪尺寸变换图像旋转 噪声处理添加噪声处理噪声 数字图像增强 亮度与对比度转换 图像变换可分为以下两种&#xff1a; 点算子&#xff1a;基于像素变换&#xff0c;在这一类图像变换中&#xff0c;仅仅根据输入像素值计算…...

maven报错:[ERROR] 不再支持源选项 7。请使用 8 或更高版本。

解决方案 pom.xml文件中增加maven编译的java.version jdk版本设置&#xff0c;以及maven.compiler.source 资源编译jdk版本设置和maven.compiler.target 资源构建jdk版本设置 JDK&#xff1a;6~8 一般都是1.6&#xff0c;1.7&#xff0c;1.8的写法。 <properties><…...

MySQL基础3-约束

MySQL基础3-约束 一. 约束概述1.1 概念1.2 目的1.3 分类 二. 约束演示三. 外键约束3.1 概念3.2 语法三. 删除/更新行为 一. 约束概述 1.1 概念 约束是作用于表中字段上的规则&#xff0c;用于限制存储在表中的数据 1.2 目的 保证数据库中数据的正确、有效性和完整…...

OJ练习第166题——课程表(拓扑排序问题)

课程表 力扣链接&#xff1a;207. 课程表 题目描述 你这个学期必须选修 numCourses 门课程&#xff0c;记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出&#xff0c;其中 prerequisites[i] [ai, bi] &#xff0c;表…...

单臂路由实现VLAN间路由

单臂路由实现VLAN间路由 单臂路由 概述拓扑图PC配置LSW2 接入层交换机LSW3 接入层交换机LSW1 汇聚层交换机R1 路由器ping 测试 单臂路由 概述 单臂路由的原理是通过一台路由器&#xff0c;使 VLAN 间互通数据通过路由器进行三层转发。 如果在路由器上为每个 VLAN 分配一个单独…...

【VSCode】文件模板创建及使用.md

背景 最近使用VSCode学习Vue项目比较频繁&#xff0c;每次创建Vue文件都要手动写重复代码&#xff0c;特别麻烦&#xff0c;就上网查找自动生成代码的说明&#xff0c;结果发现VSCode有代码模板&#xff0c;怪怪&#xff0c;感觉发现新大陆了(low!)。 配置 打开配置 方式一&a…...

【漏洞复现】EnjoySCM存在文件上传漏洞

漏洞描述 EnjoySCM是一款适应于零售企业的供应链管理软件,主要为零售企业的供应商提供服务。EnjoySCM的目的是通过信息技术,实现供应商和零售企业的快速、高效、准确的信息沟通、管理信息交流。。 该系统存在任意文件上传漏洞,攻击者通过漏洞可以获取服务器的敏感信息。 …...

MaPLe: Multi-modal Prompt Learning

本文也是LLM系统的文章&#xff0c;主要是面向多模态的大语言模型&#xff0c;针对《MaPLe: Multi-modal Prompt Learning》的翻译。 MaPLe&#xff1a;多模态提示学习 摘要1 引言2 相关工作3 方法4 实验5 结论 摘要 CLIP等预先训练的视觉语言&#xff08;V-L&#xff09;模型…...

软件测试/测试开发丨Jenkins Pipeline 学习笔记

点此获取更多相关资料 本文为霍格沃兹测试开发学社学员学习笔记分享 原文链接&#xff1a;https://ceshiren.com/t/topic/26711 1. Jenkins节点 1.1 常用的节点 内建节点SSH节点Java Web节点 1.1.1 SSH节点配置 远程工作目录 节点中必须有该目录&#xff0c;用于下载和运行j…...

java多线程——线程池

线程池 线程池创建线程池关闭线程池使用获取多个结果 线程池 一个线程池中存在许多准备运行的空闲线程&#xff0c;把Runnable对象交给线程池&#xff0c;会有一个线程调用其run()方法&#xff0c;当调用完后线程不会死亡&#xff0c;而是在池中继续为下一次请求服务 利用线程…...

Linux文件操作

目录 复制文件、目录 cp 移动 重命名文件或目录 mv 创建删除文件 touch rm(remove) 创建删除目录 mkdir(make directory) rmdir(remove directory) 复制文件、目录 cp cp(copy) 同一个目录下复制&#xff0c;所以重命名了一下&#xff1b;把它复制到linuxcast.net/目录下可以…...

Tomcat多实例 + Tomcat负载均衡、动静分离(Nginx联动)

多实例联动 一、Tomcat 多实例1.1 什么是Tomcat多实例&#xff1f;1.2 配置思路1.3 配置实现1.3.1 安装jdk1.3.2 安装tomcat1.3.3 配置 tomcat 环境变量1.3.4 修改端口号1.3.5 修改各 tomcat 实例中的 startup.sh 和 shutdown.sh 文件&#xff0c;添加 tomcat 环境变量1.3.6 启…...

bootstrap和application的区别

SpringBoot项目的配置文件支持两种四个&#xff1a; bootstrap和application。 YML文件两个&#xff1a;bootstrap.yml&#xff0c;application.yml 属性文件两个&#xff1a;bootstrap.properties&#xff0c;application.properties 配置文件优先级 SpringBoot支持同时使用…...

【狂神】SpringMVC笔记(一)之详细版

1.Restful 风格 概念&#xff1a; 实现方式&#xff1a; 使用PathVariable 在url相同的情况下&#xff0c;会根据请求方式的不同来执行不同的方法。 使用RestFull风格的好处&#xff1a;简洁、高效、安全 2、接受请求参数及数据回显 2.1、请求参数 方式一&#xff1a;这里…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...