当前位置: 首页 > 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 个元素的基数。…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

深入理解Optional:处理空指针异常

1. 使用Optional处理可能为空的集合 在Java开发中&#xff0c;集合判空是一个常见但容易出错的场景。传统方式虽然可行&#xff0c;但存在一些潜在问题&#xff1a; // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)

+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...