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

力扣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 <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWordendWord 和 wordList[i] 由小写英文字母组成
  • beginWord != endWord
  • wordList 中的所有字符串 互不相同

嘶。。。。太难了,不会。。。。 

猝!!!!! 

 

正片开始:

解题思路: 

这道题可以使用广度优先搜索(BFS)算法来解决。BFS 算法从 beginWord 开始,逐层向外扩展,直到找到 endWord。以下是如何使用 BFS 算法解决这道题的思路:

  1. 使用队列 queue 来存储待访问的单词。
  2. 使用集合 visited 来记录已访问过的单词,避免重复访问。
  3. 初始化层数 level 为 1。
  4. 将 beginWord 加入队列 queue,并将 beginWord 加入集合 visited
  5. 循环执行以下步骤,直到队列 queue 为空:
    • 将队列 queue 中的所有单词出队。
    • 对于每个出队的单词 currentWord
      • 如果 currentWord 等于 endWord,则找到最短转换序列,返回层数 level
      • 否则,获取 currentWord 的所有相邻单词 neighbors
      • 对于每个相邻单词 neighbor
        • 如果 neighbor 未被访问过,则将其加入队列 queue 和集合 visited
    • 将层数 level 加 1。
  6. 如果 BFS 结束后仍未找到 endWord,则返回 0。

具体代码实现:

import java.util.*;public class WordLadder {public int ladderLength(String beginWord, String endWord, List<String> wordList) {// 如果字典中不存在 endWord,则返回 0if (!wordList.contains(endWord)) {return 0;}// 使用队列进行广度优先搜索(BFS)Queue<String> queue = new LinkedList<>();queue.offer(beginWord);// 使用集合记录已访问过的单词,避免重复访问Set<String> visited = new HashSet<>();visited.add(beginWord);// 层数,从 1 开始int level = 1;while (!queue.isEmpty()) {int size = queue.size();// 当前层的单词全部出队for (int i = 0; i < size; i++) {String currentWord = queue.poll();// 如果当前单词等于 endWord,则找到最短转换序列,返回层数if (currentWord.equals(endWord)) {return level;}// 遍历当前单词的相邻单词List<String> neighbors = getNeighbors(currentWord, wordList);for (String neighbor : neighbors) {// 如果相邻单词未被访问过,则将其加入队列和 visited 集合if (!visited.contains(neighbor)) {queue.offer(neighbor);visited.add(neighbor);}}}// 层数加 1level++;}// 如果 BFS 结束后仍未找到 endWord,则返回 0return 0;}// 获取当前单词的相邻单词private List<String> getNeighbors(String word, List<String> wordList) {List<String> neighbors = new ArrayList<>();for (String candidate : wordList) {int diffCount = 0;// 比较两个单词,计算不同字符的数量for (int i = 0; i < word.length(); i++) {if (word.charAt(i) != candidate.charAt(i)) {diffCount++;}}// 如果不同字符的数量为 1,则 candidate 是相邻单词if (diffCount == 1) {neighbors.add(candidate);}}return neighbors;}
}

时间复杂度: 

噗噗噗..........

这时间复杂度比我命还长啊。。。。。。。。。。。。。。。。。。。。。

=========================================================================

这道题使用广度优先搜索(BFS)算法,其时间复杂度为 O(V + E),其中:

  • V 是单词列表中的单词数量(即顶点数)
  • E 是单词列表中单词之间的转换关系数量(即边数)

在最坏的情况下,我们需要遍历整个单词列表,并且每个单词与其他所有单词都存在转换关系。因此,时间复杂度为 O(V^2)。

然而,在实际情况下,单词列表中的单词通常只与少数其他单词存在转换关系。因此,时间复杂度通常会更接近 O(V + E)。

总的来说,这道题的 时间复杂度为 O(V + E),在最坏的情况下为 O(V^2)。

 

总结 

这道题要求找出从一个单词到另一个单词的最短转换序列,转换规则是每次只能改变一个字母,且转换后的单词必须在给定的单词列表中。

我们可以使用广度优先搜索(BFS)算法来解决这道题。BFS 算法从起始单词开始,逐层向外扩展,直到找到目标单词。

 

 

 

相关文章:

力扣127.单词接龙讲解

距离上一次刷题已经过去了.........嗯............我数一一下............整整十天&#xff0c;今天再来解一道算法题 由于这段时间准备简历&#xff0c;没咋写博客。。今天回来了&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&…...

latex笔记

双列排版&#xff0c;右端margin不对齐怎么解决 如下图这种情况&#xff0c; 解决方法&#xff1a; 在文档开头引入ragged2e包 \usepackage{ragged2e}然后在子章节的开头添加 \justifying\subsection{camouflaged object detection based on coarse-to-fine strategy} \just…...

秋招算法——AcWing101——拦截导弹

文章目录 题目描述思路分析实现源码分析总结 题目描述 思路分析 目前是有一个笨办法&#xff0c;就是创建链表记录每一个最长下降子序列所对应的节点的链接&#xff0c;然后逐个记录所有结点的访问情况&#xff0c;直接所有节点都被访问过。这个方法不是很好&#xff0c;因为需…...

IDEA不能创建新项目和新模块

问题&#xff1a; IDEA不管是创建新项目还是新模块都创建不成功&#xff0c;会报如下图错误 解决方案&#xff1a; 在电脑设置里搜索 “防火墙和网络保护” &#xff0c;打开如下图所示 找到你所安装的IDEA&#xff0c;更改设置&#xff0c;选中IDEA 最后&#xff0c;确定&am…...

WebRTC 的核心:RTCPeerConnection

WebRTC 的核心&#xff1a;RTCPeerConnection WebRTC 的核心&#xff1a;RTCPeerConnection创建 RTCPeerConnection 对象RTCPeerConnection 与本地音视频数据绑定媒体协商ICE什么是 Candidate&#xff1f;收集 Candidate交换 Candidate尝试连接 SDP 与 Candidate 消息的互换远端…...

LeetCode hot100-39-N

101. 对称二叉树给你一个二叉树的根节点 root &#xff0c; 检查它是否轴对称。做不出来哇&#xff0c;递归一生之敌 普通的对一棵树的递归遍历根本没办法只接比较左子树的左和右子树的右这样来比较&#xff0c;所以这题比较巧妙的是把这棵树当做两棵树一样去遍历比较。 官方…...

NumPy常用操作

目录 一:简介 二:NumPy 常用操作 三:总结 一:简介 是一个开源的Python库,它为Python提供了强大的多维数组对象和用于处理这些数组的函数。NumPy的核心是ndarray,它是一个高效的多维数组容器,用于存储和处理大规模的数据。NumPy还提供了许多数学函数,用于数组之间的操…...

学习笔记——字符串(单模+多模+练习题)

单模匹配 Brute Force算法&#xff08;暴力&#xff09; 算法思想 母串和模式串字符依次配对&#xff0c;如果配对成功则继续比较后面位置是否相同&#xff0c;如果出现匹配不成功的位置&#xff0c;则j&#xff08;模式串当前的位置&#xff09;从头开始&#xff0c;i&…...

DOT + graphviz 轻松画图

GraphViz&#xff1a;2 DOT语法和相关应用_graphviz dot-CSDN博客 图可视化之Graphviz - 知乎 Graphviz 是由AT&T Research、Lucent Bell实验室开源的可视化图形工具&#xff0c;可以很方便的用来绘制结构化的图形网络。具体地&#xff0c;其使用一种名为dot语言的DSL来编…...

使用Vue调用ColaAI Plus大模型,实现聊天(简陋版)

首先去百度文心注册申请自己的api 官网地址&#xff1a;LuckyCola 注册点开个人中心 查看这个文档自己申请一个ColaAI Plus定制增强大模型API | LuckyColahttps://luckycola.com.cn/public/docs/shares/api/colaAi.html来到vue的页面 写个样式 <template><Header …...

Unity使用sherpa-onnx实现离线语音合成

sherpa-onnx https://github.com/k2-fsa/sherpa-onnx 相关dll和lib库拷进Unity&#xff0c;官方示例代码稍作修改 using SherpaOnnx; using System; using System.IO; using System.Runtime.InteropServices; using UnityEngine;public class TTS : MonoBehaviour {public st…...

Elasticsearch入门基础和集群部署

Elasticsearch入门基础和集群部署 简介基础概念索引&#xff08;Index&#xff09;类型&#xff08;Type&#xff09;&#xff08;逐步弃用&#xff09;文档&#xff08;Document&#xff09;字段&#xff08;Field&#xff09;映射&#xff08;Mapping&#xff09;分片&#x…...

12、24年--信息系统治理——IT治理

主要考选择题,2分左右,案例、论文涉及概率不大,需要认证读课本原文。 1、IT治理基础 IT治理是描述组织采用有效的机制对信息技术和数据资源开发利用,平衡信息化发展和数字化转型过程中的风险,确保实现组织的战略目标的过程。 1.1 IT治理的驱动因素 1)存在很多问题: 信…...

Electron学习笔记(三)

文章目录 相关笔记笔记说明 五、界面1、获取 webContents 实例&#xff08;1&#xff09;通过窗口对象的 webContent 属性获取 webContent 实例&#xff1a;&#xff08;2&#xff09;获取当前激活窗口的 webContents 实例&#xff1a;&#xff08;3&#xff09;在渲染进程中获…...

【Redis】Redis键值存储

大家好&#xff0c;我是白晨&#xff0c;一个不是很能熬夜&#xff0c;但是也想日更的人。如果喜欢这篇文章&#xff0c;点个赞&#x1f44d;&#xff0c;关注一下&#x1f440;白晨吧&#xff01;你的支持就是我最大的动力&#xff01;&#x1f4aa;&#x1f4aa;&#x1f4aa…...

C++系统编程篇——Linux初识(系统安装、权限管理,权限设置)

(1)linux系统的安装 双系统---不推荐虚拟机centos镜像&#xff08;可以使用&#xff09;云服务器/轻量级云服务器&#xff08;强烈推荐&#xff09; ①云服务器&#xff08;用xshell连接&#xff09; ssh root公网IP 然后输入password ①添加用户&#xff1a; addus…...

No Cortex-M SW Device Found

将DIO和CLK管脚调换一下...

提升写作效率的秘密武器:一个资深编辑的AI写作体验

有句话说:“写作是一项你坐在打字机前流血的工作。”而如今,各类生成式软件的涌现似乎打破了写作这一古老的艺术形式壁垒。过去,作家们独自在书桌前冥思苦想,如今,一款名为“玲珑AI工具”的ai写作助手正悄然改变着文案写作行业的创作生态,成为提升写作效率的秘密武器。 在传统…...

Python sort() 和 sorted() 的区别应用实例详解

大家好&#xff0c;今天针对 Python 中 sort() 和 sorted() 之间的区别&#xff0c;来一个实例详细解读。sort — 顾名思义就是排序的意思&#xff0c;它可以接收的对象为可迭代的数据类型。今天以列表为例子演示两者的不同点、相同点&#xff0c;以及其中一些常用的高级参数使…...

七、Redis三种高级数据结构-HyperLogLog

Redis HyperLogLog是用来做基数统计的算法&#xff0c;HyperLogLog在优点是&#xff0c;在输入的元素的数量或者体积非常大时&#xff0c;计算基数占用的空间总是固定的、并且非常小。在Redis里每个HyperLogLog键只需花费12KB内存&#xff0c;就可以计算接近 264 个元素的基数。…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...

【深尚想】TPS54618CQRTERQ1汽车级同步降压转换器电源芯片全面解析

1. 元器件定义与技术特点 TPS54618CQRTERQ1 是德州仪器&#xff08;TI&#xff09;推出的一款 汽车级同步降压转换器&#xff08;DC-DC开关稳压器&#xff09;&#xff0c;属于高性能电源管理芯片。核心特性包括&#xff1a; 输入电压范围&#xff1a;2.95V–6V&#xff0c;输…...

raid存储技术

1. 存储技术概念 数据存储架构是对数据存储方式、存储设备及相关组件的组织和规划&#xff0c;涵盖存储系统的布局、数据存储策略等&#xff0c;它明确数据如何存储、管理与访问&#xff0c;为数据的安全、高效使用提供支撑。 由计算机中一组存储设备、控制部件和管理信息调度的…...