字符串接龙 /单词接龙 (BFs C#

卡码网 110和 力扣127 和LCq 108题都是一个解法 

这两道题乍一看在结果处可能不一样 力扣要求 字符串里边必须包含对应的最后一个字符 

而110不需要最后一个字符 但是在实验逻辑上是一致的 只是110需要把如果在set中找不到最后一个字符就直接返回0的逻辑删去 就可以了  这就是两道题的区别

110. 字符串接龙

题目描述

字典 strList 中从字符串 beginStr 和 endStr 的转换序列是一个按下述规格形成的序列: 

1. 序列中第一个字符串是 beginStr。

2. 序列中最后一个字符串是 endStr。 

3. 每次转换只能改变一个字符。 

4. 转换过程中的中间字符串必须是字典 strList 中的字符串,且strList里的每个字符串只用使用一次。 

给你两个字符串 beginStr 和 endStr 和一个字典 strList,找到从 beginStr 到 endStr 的最短转换序列中的字符串数目。如果不存在这样的转换序列,返回 0。

输入描述

第一行包含一个整数 N,表示字典 strList 中的字符串数量。 第二行包含两个字符串,用空格隔开,分别代表 beginStr 和 endStr。 后续 N 行,每行一个字符串,代表 strList 中的字符串。

输出描述

输出一个整数,代表从 beginStr 转换到 endStr 需要的最短转换序列中的字符串数量。如果不存在这样的转换序列,则输出 0。

输入示例
6
abc def
efc
dbc
ebc
dec
dfc
yhn
输出示例
4
提示信息

从 startStr 到 endStr,在 strList 中最短的路径为 abc -> dbc -> dec -> def,所以输出结果为 4,如图:

数据范围:

2 <= N <= 500

思路: 

通过无向图来理解就很容易明白了 先从begin元素开始入队列 出队列时找与begin相链接(就差一个字母的)入队列并且增加path长度 加1 存进预制好的字典当中 ,然后循环往复 知道遇见改完一个字母就直接等于end元素的 元素 记录他的path+1 直接就是结果 详细:本题只需要求出最短长度就可以了,不用找出路径。
所以这道题要解决两个问题:
图中的线是如何连在一起的
起点和终点的最短路径长度
首先题目中并没有给出点与点之间的连线,而是要我们自己去连,条件是字符只能差一个,所以判断点与点之间的关系,要自己判断是不是差一个字符,如果差一个字符,那就是有链接。
然后就是求起点和终点的最短路径长度,这里无向图求最短路,广搜最为合适,广搜只要搜到了终点,那么一定是最短的路径。因为广搜就是以起点中心向四周扩散的搜索。

 

using System;
using System.Collections.Generic;

public class MainClass
{
    public static void Main(string[] args)
    {
        //输入代码 
        int n=int.Parse(Console.ReadLine());
        string[] strs=Console.ReadLine().Split(' ');
        List<string> wordList=new List<string>();
        for(int i=0;i<n;i++)
        {
            wordList.Add(Console.ReadLine());
        }
        //输出结果
        int result=LadderLength(strs[0],strs[1],wordList);
        Console.WriteLine(result);
    }
    // BFS方法
    public static int LadderLength(string beginWord, string endWord, List<string> wordList)
    {
        // 使用HashSet作为查询容器,效率更高
        HashSet<string> set = new HashSet<string>(wordList);
        
        // 声明一个Queue存储每次变更一个字符得到的且存在于容器中的新字符串
        Queue<string> queue = new Queue<string>();
        
        // 声明一个Dictionary存储遍历到的字符串以及所走过的路径
        Dictionary<string, int> visitmap = new Dictionary<string, int>();
        
        queue.Enqueue(beginWord);
        visitmap[beginWord] = 1; //将begin字符存入字典中 其值为1 
        
        while (queue.Count > 0)
        {
            string word = queue.Dequeue();//取出队头单词 
            int path = visitmap[word];//获取到该单词的路径长度

            for (int i = 0; i < word.Length; i++)
            {
                char[] chars = word.ToCharArray();
                // 每个位置尝试26个字母
                for (char k = 'a'; k <= 'z'; k++)
                {
                    chars[i] = k;
                    string newword = new string(chars);//得到新的字符串 
                    //如果新的字符串值与endword一致 返回当前长度加1(直接结束相当于)
                    if (newword == endWord) //如果找到了 
                    {
                        return path + 1;
                    }
                    //另一种情况 如果新单词在set中(说明此时这俩需要链接 因为就换了一个字母然后就相等了 代表这两个单词其实就差一个字母的不同)   但是没有被访问过 
                    //如果哈希表中包含同时 字典中不包含这个字符串 那么就记录到字典中 
                    if (set.Contains(newword) && !visitmap.ContainsKey(newword))
                    {
                        visitmap[newword] = path + 1;
                        queue.Enqueue(newword);
                    }
                }
            }
        }

        return 0;
    }


}

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

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

相关文章

Transformer和BERT的区别

Transformer和BERT的区别比较表&#xff1a; 两者的位置编码&#xff1a; 为什么要对位置进行编码&#xff1f; Attention提取特征的时候&#xff0c;可以获取全局每个词对之间的关系&#xff0c;但是并没有显式保留时序信息&#xff0c;或者说位置信息。就算打乱序列中token…

python操作MySQL以及SQL综合案例

1.基础使用 学习目标&#xff1a;掌握python执行SQL语句操作MySQL数据库软件 打开cmd下载安装 安装成功 connection就是一个类&#xff0c;conn类对象。 因为位置不知道&#xff0c;所以使用关键字传参。 表明我们可以正常连接到MySQL 演示、执行非查询性质的SQL语句 pytho…

【报告PDF附下载】2024人工智能大模型技术财务应用蓝皮书

《人工智能大模型技术财务应用蓝皮书》 是一本探讨AI大模型技术在财务管理领域应用的权威指南。书中不仅概述了人工智能大模型技术的发展历程、典型特征和未来趋势&#xff0c;还详细介绍了它的体系架构和在财务领域的应用情况。 书中通过家用电器制造、银行、汽车企业、基础设…

快速上手vue3+js+Node.js

安装Navicat Premium Navicat Premium 创建一个空的文件夹&#xff08;用于配置node&#xff09; 生成pakeage.json文件 npm init -y 操作mysql npm i mysql2.18.1 安装express搭建web服务器 npm i express4.17.1安装cors解决跨域问题 npm i cors2.8.5创建app.js con…

【Python爬虫实战】DrissionPage 与 ChromiumPage:高效网页自动化与数据抓取的双利器

&#x1f308;个人主页&#xff1a;易辰君-CSDN博客 &#x1f525; 系列专栏&#xff1a;https://blog.csdn.net/2401_86688088/category_12797772.html ​ 目录 前言 一、DrissionPage简介 &#xff08;一&#xff09;特点 &#xff08;二&#xff09;安装 &#xff08;三…

【JAVA】java 企业微信信息推送

前言 JAVA中 将信息 推送到企业微信 // 企微消息推送messageprivate String getMessage(String name, String problemType, String pushResults, Long orderId,java.util.Date submitTime, java.util.Date payTime) {String message "对接方&#xff1a;<font color\…

前端md5加密

npm下载 npm install --save ts-md5页面引入 import { Md5 } from ts-md5使用 const md5PwdMd5.hashStr("123456")md5Pwd&#xff08;加密后的数据&#xff09; .toUpperCase()方法转大写

DDRSYS,不同频点的时序参数配置说明,DBI/DM功能说明

文章目录 不同频点的时序参数配置说明LPDDR4 时序参数DFI 参数对应配置DDR3/4DBI功能说明&#xff0c;MC控制DBI情况 不同频点的时序参数配置说明 LPDDR4 时序参数 LP4的时序参数从JEDEC颗粒文档可以检索到读写的时序参数如下&#xff1a; 此图主要关注不同频点对应的RL和WL…

如何自学机器学习?

自学机器学习可以按照以下步骤进行&#xff1a; 一、基础知识准备 数学基础&#xff1a; 高等数学&#xff1a;学习微积分&#xff08;包括导数、微分、积分等&#xff09;、极限、级数等基本概念。这些知识是后续学习算法和优化方法的基础。 线性代数&#xff1a;掌握矩阵…

工程巡查应该怎么做?如何利用巡查管理软件?

工程行业&#xff0c;无论是建设单位&#xff0c;监理单位&#xff0c;还是施工单位&#xff0c;工程巡查几乎是每日必做的工作。然而&#xff0c;巡查过程中&#xff0c;传统的做法通常依赖手动记录、拍照上传、在微信群中进行汇报。这种方式需要建大量的微信群&#xff0c;不…

Scala入门基础(16)scala的包

Scala的包定义包定义包对象Scala的包的导入导入重命名 一.Scala的包 package&#xff08;包&#xff1a;一个容器。可以把类&#xff0c;对象&#xff0c;包&#xff0c;装入。 好处&#xff1a; 区分同名的类&#xff1b;类很多时&#xff0c;更好地管理类&#xff1b;控制…

协程6 --- HOOK

文章目录 HOOK 概述链接运行时动态链接 linux上的常见HOOK方式修改函数指针用户态动态库拦截getpidmalloc 第一版malloc 第二版malloc/free通过指针获取到空间大小malloc 第三版strncmp 内核态系统调用拦截堆栈式文件系统 协程的HOOK HOOK 概述 原理&#xff1a;修改符号指向 …

MySQL中,GROUP BY 分组函数

文章目录 示例查询&#xff1a;按性别分组统计每组信息示例查询&#xff1a;按性别分组显示详细信息示例查询&#xff1a;按性别分组并计算平均年龄,如果你还想统计每个性别的平均年龄&#xff0c;可以结合AVG()函数&#xff1a;说明 示例查询&#xff1a;按性别分组统计每组信…

免费数据集网站

1、DataSearch https://datasetsearch.research.google.comhttp://DataSearch 2、FindData findata-科学数据搜索引擎https://www.findata.cn/ 3、Kaggle Kaggle: Your Machine Learning and Data Science CommunityKaggle is the world’s largest data science community …

十二:java web(4)-- Spring核心基础

目录 创建项目 Spring 核心基础 Spring 容器 Spring 容器的作用 Spring 容器的工作流程 Bean Bean 的生命周期 IOC&#xff08;控制反转&#xff09;与依赖注入&#xff08;DI&#xff09; 控制反转的概念 依赖注入的几种方式&#xff08;构造器注入、Setter 注入、接…

MybatisPlus入门(八)MybatisPlus-DQL编程控制

一、字段映射与表名映射 数据库表和实体类名称一样自动关联&#xff0c;数据库表和实体类有部分情况不一样。 问题一&#xff1a;表名与编码开发设计不同步&#xff0c;表名和实体类名称不一致。 解决办法&#xff1a; 在模型类上方&#xff0c;使用TableName注解&#xf…

亚信安全新一代WAF:抵御勒索攻击的坚固防线

近年来&#xff0c;勒索攻击已成为黑客的主要攻击手段。新型勒索攻击事件层出不穷&#xff0c;勒索攻击形势愈发严峻&#xff0c;已经对全球制造、金融、能源、医疗、政府组织等关键领域造成严重危害。如今&#xff0c;勒索攻击手段日趋成熟、攻击目标愈发明确&#xff0c;模式…

代谢组数据分析(二十一):通过MetaboAnalystR标准化构建sPLSDA预测模型

禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍MetaboAnalystR标准化sPLSDA分析安装需要的R包加载R包导入数据MetaboAnalystR标准化数据初始化数据清洗数据补足数据过滤数据标准化导出结果sPLSDA分析导入数据数据预处理PCA分析PL…

《ElementPlus 与 ElementUI 差异集合》Icon 图标 More 差异说明

参考 《element plus 使用 icon 图标(两种方式)》使用 icon 升级 Vue2 升级 Vue3 项目时&#xff0c;遇到命名时的实心与空心点差异&#xff01; ElementUI&#xff1a; 实心是 el-icon-more空心是 el-icon-more-outline ElementPlus&#xff1a; 实心是 el-icon-more-fill…

Java项目实战II基于Spring Boot的光影视频平台(开发文档+数据库+源码)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。获取源码联系方式请查看文末 一、前言 在数字化时…