leetcode127单词接龙刷题打卡
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中的所有字符串 互不相同
题解思路
在学习图论的时候做的一道题,完全没有思路,之前做的题都是二维矩阵,有个图样,轮到每个点有四个方向供我选择,这道题只有一个单词列表。
待解决问题:
-
深搜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: 每一对相邻的单词只差一个字母。对于 1 < i < k 时,每个 si 都在 wordList 中。注意&am…...
基于SSM的物流管理系统
末尾获取源码 开发语言:Java Java开发工具:JDK1.8 后端框架:SSM 前端:采用JSP技术开发 数据库:MySQL5.7和Navicat管理工具结合 服务器:Tomcat8.5 开发软件:IDEA / Eclipse 是否Maven项目&#x…...
EagleSDR USB HAT FT600
给EagleSDR做了个USB 3.0的子卡,采用FT600方案,实物如下: 用FT600DataStreamerDemoApp测试,速度如下: 由于FT600是16bit的接口,如果用FT601的32bit接口,性能应该还会有大幅提升。 测试代码很简…...
Java多线程(四)锁策略(CAS,死锁)和多线程对集合类的使用
锁策略(CAS,死锁)和多线程对集合类的使用 锁策略 1.乐观锁VS悲观锁 2.轻量级锁VS重量级锁 3.自旋锁VS挂起等待锁 4.互斥锁VS读写锁 5.可重入锁vs不可重入锁 死锁的第一种情况 死锁的第二种情况 死锁的第三种情况 CAS 1.实现原子类 …...
基于spring boot+ vue+ mysql开发的UWB室内外定位系统源码
现代制造业厂区面积大、人员数量多、物资设备不断增加,随着工业信息化技术的发展,大型制造企业中对人员、车辆、物资的管理要求越来越细致。 高精度定位管理系统使用UWB室内定位技术,通过在厂区安装定位基站,为人员或设备佩戴定位…...
第2章_瑞萨MCU零基础入门系列教程之面向过程与面向对象
本教程基于韦东山百问网出的 DShanMCU-RA6M5开发板 进行编写,需要的同学可以在这里获取: https://item.taobao.com/item.htm?id728461040949 配套资料获取:https://renesas-docs.100ask.net 瑞萨MCU零基础入门系列教程汇总: ht…...
数字图像处理:亮度对比度-几何变换-噪声处理
文章目录 数字图像增强亮度与对比度转换几何变换图像裁剪尺寸变换图像旋转 噪声处理添加噪声处理噪声 数字图像增强 亮度与对比度转换 图像变换可分为以下两种: 点算子:基于像素变换,在这一类图像变换中,仅仅根据输入像素值计算…...
maven报错:[ERROR] 不再支持源选项 7。请使用 8 或更高版本。
解决方案 pom.xml文件中增加maven编译的java.version jdk版本设置,以及maven.compiler.source 资源编译jdk版本设置和maven.compiler.target 资源构建jdk版本设置 JDK:6~8 一般都是1.6,1.7,1.8的写法。 <properties><…...
MySQL基础3-约束
MySQL基础3-约束 一. 约束概述1.1 概念1.2 目的1.3 分类 二. 约束演示三. 外键约束3.1 概念3.2 语法三. 删除/更新行为 一. 约束概述 1.1 概念 约束是作用于表中字段上的规则,用于限制存储在表中的数据 1.2 目的 保证数据库中数据的正确、有效性和完整…...
OJ练习第166题——课程表(拓扑排序问题)
课程表 力扣链接:207. 课程表 题目描述 你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] [ai, bi] ,表…...
单臂路由实现VLAN间路由
单臂路由实现VLAN间路由 单臂路由 概述拓扑图PC配置LSW2 接入层交换机LSW3 接入层交换机LSW1 汇聚层交换机R1 路由器ping 测试 单臂路由 概述 单臂路由的原理是通过一台路由器,使 VLAN 间互通数据通过路由器进行三层转发。 如果在路由器上为每个 VLAN 分配一个单独…...
【VSCode】文件模板创建及使用.md
背景 最近使用VSCode学习Vue项目比较频繁,每次创建Vue文件都要手动写重复代码,特别麻烦,就上网查找自动生成代码的说明,结果发现VSCode有代码模板,怪怪,感觉发现新大陆了(low!)。 配置 打开配置 方式一&a…...
【漏洞复现】EnjoySCM存在文件上传漏洞
漏洞描述 EnjoySCM是一款适应于零售企业的供应链管理软件,主要为零售企业的供应商提供服务。EnjoySCM的目的是通过信息技术,实现供应商和零售企业的快速、高效、准确的信息沟通、管理信息交流。。 该系统存在任意文件上传漏洞,攻击者通过漏洞可以获取服务器的敏感信息。 …...
MaPLe: Multi-modal Prompt Learning
本文也是LLM系统的文章,主要是面向多模态的大语言模型,针对《MaPLe: Multi-modal Prompt Learning》的翻译。 MaPLe:多模态提示学习 摘要1 引言2 相关工作3 方法4 实验5 结论 摘要 CLIP等预先训练的视觉语言(V-L)模型…...
软件测试/测试开发丨Jenkins Pipeline 学习笔记
点此获取更多相关资料 本文为霍格沃兹测试开发学社学员学习笔记分享 原文链接:https://ceshiren.com/t/topic/26711 1. Jenkins节点 1.1 常用的节点 内建节点SSH节点Java Web节点 1.1.1 SSH节点配置 远程工作目录 节点中必须有该目录,用于下载和运行j…...
java多线程——线程池
线程池 线程池创建线程池关闭线程池使用获取多个结果 线程池 一个线程池中存在许多准备运行的空闲线程,把Runnable对象交给线程池,会有一个线程调用其run()方法,当调用完后线程不会死亡,而是在池中继续为下一次请求服务 利用线程…...
Linux文件操作
目录 复制文件、目录 cp 移动 重命名文件或目录 mv 创建删除文件 touch rm(remove) 创建删除目录 mkdir(make directory) rmdir(remove directory) 复制文件、目录 cp cp(copy) 同一个目录下复制,所以重命名了一下;把它复制到linuxcast.net/目录下可以…...
Tomcat多实例 + Tomcat负载均衡、动静分离(Nginx联动)
多实例联动 一、Tomcat 多实例1.1 什么是Tomcat多实例?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 文件,添加 tomcat 环境变量1.3.6 启…...
bootstrap和application的区别
SpringBoot项目的配置文件支持两种四个: bootstrap和application。 YML文件两个:bootstrap.yml,application.yml 属性文件两个:bootstrap.properties,application.properties 配置文件优先级 SpringBoot支持同时使用…...
【狂神】SpringMVC笔记(一)之详细版
1.Restful 风格 概念: 实现方式: 使用PathVariable 在url相同的情况下,会根据请求方式的不同来执行不同的方法。 使用RestFull风格的好处:简洁、高效、安全 2、接受请求参数及数据回显 2.1、请求参数 方式一:这里…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...
Sklearn 机器学习 缺失值处理 获取填充失值的统计值
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...
OCR MLLM Evaluation
为什么需要评测体系?——背景与矛盾 能干的事: 看清楚发票、身份证上的字(准确率>90%),速度飞快(眨眼间完成)。干不了的事: 碰到复杂表格(合并单元…...
uni-app学习笔记三十五--扩展组件的安装和使用
由于内置组件不能满足日常开发需要,uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件,需要安装才能使用。 一、安装扩展插件 安装方法: 1.访问uniapp官方文档组件部分:组件使用的入门教程 | uni-app官网 点击左侧…...
