每日OJ题_BFS解决最短路③_力扣127. 单词接龙

目录

③力扣127. 单词接龙

解析代码


③力扣127. 单词接龙

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 中的所有字符串 互不相同
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {

    }
};

解析代码

        和力扣433. 最小基因变化一样,如果将每次字符串的变换抽象成图中的两个顶点和一条边的话,问题就变成了边权为 1 的最短路问题。 因此,从起始的字符串开始,来一次 bfs 即可。

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordListHash(wordList.begin(), wordList.end());
        unordered_set<string> vis;
        if(!wordListHash.count(endWord))
            return 0;

        int ret = 1;
        queue<string> q;
        q.push(beginWord);
        vis.insert(beginWord);
        while(!q.empty())
        {
            ++ret;
            int size = q.size();
            while(size--)
            {
                string t = q.front();
                q.pop();
                for(int i = 0; i < t.size(); ++i)
                {
                    for(char ch = 'a'; ch <= 'z'; ++ch)
                    {
                        string tmp = t;
                        tmp[i] = ch;
                        if(wordListHash.count(tmp) && !vis.count(tmp))
                        {
                            if(tmp == endWord)
                                return ret;
                            q.push(tmp);
                            vis.insert(tmp);
                        }
                    }
                }
            }
        }
        return 0;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/547366.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

GPT人工智能在线网页版大全

平民不参与内测&#xff0c;还能使用 ChatGPT 吗&#xff1f; 自去年 ChatGPT 爆红以来&#xff0c;关于它的消息铺天盖地。如果你真的想使用它&#xff0c;途径有很多。除了官方网站外国内还有许多 ChatGPT 的镜像网站&#xff0c;其中不乏免费的 3.5 版本。虽然有些网站需要…

Spring Task 定时任务调度

一、概念 Spring Task 是 Spring 框架的一个组件&#xff0c;它为任务调度提供了支持&#xff0c;使得开发者能够创建后台任务或定期执行的任务。通过 Spring Task&#xff0c;您可以方便地在 Java 应用程序中实现定时任务&#xff0c;比如每天凌晨进行数据同步、每小时执行一…

EasyRecovery数据恢复软件2024免费版下载亲测可用(支持win7,win10)

EasyRecovery数据恢复软件是由全球著名的数据恢复公司Ontrack出品的一款专业级数据文件恢复工具。它支持恢复多种存储介质上的数据&#xff0c;包括硬盘、光盘、U盘/移动硬盘、数码相机以及Raid文件恢复等&#xff0c;能恢复的文件类型也相当丰富&#xff0c;包括文档、表格、图…

基于Springboot+Vue的Java项目-校园周边美食探索及分享平台系统开发实战(附演示视频+源码+LW)

大家好&#xff01;我是程序员一帆&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;Java毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计 &am…

项目:仿muduo库One-Thread-One-Loop式并发服务器

文章目录 写在前面开源仓库和项目上线其他文档说明 项目背景HTTP服务器Reactor模型Reactor模型的分类 项目介绍模式设计模块划分Server模块 模块分析 补充知识Linux提供的定时器时间轮的思想通用类型any类型 Server模块Buffer模块Socket模块Channel模块Poller模块EventLoop模块…

项目——boost搜索引擎

今天我们来写一个boost搜索引擎&#xff01; &#xff08;后续如果有更新&#xff0c;这个博客也会更新&#xff09; gitee连接:boost搜索引擎: boost搜索引擎 首先我们要介绍一下我们这个项目&#xff0c;我们项目的目的是通过我们的搜索引擎能够通过关键字查找到对应的网页…

Open3D (C++) 点云投影至主成分空间

目录 一、算法原理二、代码实现三、结果展示四、相关连接Open3D (C++) 点云投影至主成分空间由CSDN点云侠原创,爬虫自重。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫。 一、算法原理 p r o j

【数据结构】树与二叉树、树与森林部分习题与算法设计例题

目录 【数据结构】树与二叉树部分习题与算法设计例题一、单选题二、算法设计题判断二叉树是否为完全二叉树求二叉树的最小深度 以及 二叉树树高 树与二叉树知识点文章: 【数据结构】树与二叉树&#xff08;递归法先序、中序、后序、层次遍历二叉树、二叉树的建立以及求树高的方…

【MySQL数据库 | 第二十四篇】Limit语句的性能问题和调优策略

前言&#xff1a; MySQL作为最流行的关系型数据库管理系统之一&#xff0c;被广泛应用于各种规模和类型的应用程序中。其强大的功能和灵活的查询语言使得开发人员能够高效地执行各种数据操作和分析。 然而&#xff0c;在处理大量数据或复杂查询时&#xff0c;一些开发人员可能…

研究生,该学单片机还是plc。?

PLC门槛相对较低&#xff0c;但是在深入学习和应用时&#xff0c;仍然有很高的技术要求。我这里有一套单片机入门教程&#xff0c;不仅包含了详细的视频 讲解&#xff0c;项目实战。如果你渴望学习单片机&#xff0c;不妨点个关注&#xff0c;给个评论222&#xff0c;私信22&am…

仿真服务器介绍及应用

仿真服务器是一种高性能的计算设备&#xff0c;专门用于运行复杂的仿真软件和处理大量的计算任务。 仿真服务器通常具备以下特点&#xff1a; 1. 高性能硬件配置&#xff1a;为了满足仿真软件对计算能力的要求&#xff0c;仿真服务器通常配备高性能的CPU、大量的内存以及高速的…

Zookeeper与Kafka消息队列

目录 一、Zookeeper 1、zookeeper简介 2、zookeeper的特点 3、zookeeper的工作模式跟工作机制 3.1 工作模式&#xff1a; 3.2工作机制&#xff1a;​编辑 4、zookeeper应用场景及选举机制 4.1 应用场景&#xff1a; 4.2 选举机制&#xff1a; 4.2.1第一次启动选举机制…

[阅读笔记1][GPT-3]Language Models are Few-Shot Learners

首先讲一下GPT3这篇论文&#xff0c;文章标题是语言模型是小样本学习者&#xff0c;openai于2020年发表的。 这篇是在GPT2的基础上写的&#xff0c;由于GPT2还存在一些局限&#xff0c;这篇对之前的GPT2进行了一些完善。GPT2提出了多任务学习&#xff0c;也就是可以零样本地用在…

ABAP MESSAGE 常用的类型

类型文本描述A终止处理终止&#xff0c;用户必须重启事务X退出与消息类型A 类似&#xff0c;但带有程序崩溃 MESSAGE_TYPE_XE错误处理受到干扰&#xff0c;用户必须修正输入条目,左下角提示!W警告处理受到干扰&#xff0c;用户可以修正输入条目,左下角提示!I信息处理受到干扰&a…

数字的字面表示:正负数、进位制、数学浮点数与科学计数法

示例&#xff1a; /*** brief how about plain-number? show you here.* author wenxuanpei* email 15873152445163.com(query for any question here)*/ #define _CRT_SECURE_NO_WARNINGS//support c-library in Microsoft-Visual-Studio #include <stdio.h>static…

【代码随想录】【动态规划】day43:● 1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零

最后一块石头的重量 与分割等和子集类似 思路&#xff1a;尽量分割成两个sum值相近的数组1和2&#xff0c;求其中一个数组为sum(stone)//2时的一种情况 dp[j]:容量&#xff08;这里说容量更形象&#xff0c;其实就是重量&#xff09;为j的背包&#xff0c;最多可以背最大重量…

DFS专题:力扣岛屿问题(持续更新)

DFS专题&#xff1a;力扣岛屿问题 一、岛屿数量 题目链接: 200.岛屿数量 题目描述 代码思路 使用for对每一个网格点进行判断&#xff0c;如果遇到未搜索过的’1’&#xff0c;则使岛屿数加一&#xff0c;并利用dfs将与其相连的‘1’都进行标记&#xff0c;确保每次搜索到1都…

51单片机-LED模块

文章目录 1.点亮一个LED灯2.LED闪烁3.LED流水灯 1.点亮一个LED灯 #include <REGX52.H> void main() {P20xFE; //1111 1110while(1){} }2.LED闪烁 增加延时&#xff0c;控制LED的亮灭间隙 延时函数的添加依靠STC-ISP软件的延时函数功能代码自动生成&#xff0c;如图 #i…

数据库查询:查询入参类型和数据库字段类型不匹配导致的问题

问题&#xff1a;假设我们现在有这样的一张表 CREATE TABLE test_person (id int(20) NOT NULL COMMENT 主键,name varchar(20) DEFAULT NULL COMMENT 姓名,gender char(2) DEFAULT NULL COMMENT 性别,birthday date DEFAULT NULL COMMENT 生日,created_time timestamp NULL D…

【电控笔记8】前馈技术

2.4前馈 前馈可以减轻控制器的负担