字符串接龙 /单词接龙 (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;
    }


}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

STM32之看门狗

STM32有独立看门狗&#xff08;IWDG&#xff09;和窗口看门狗(WWDG)。 采用窗口看门狗&#xff08;WWDG&#xff09;&#xff0c;有一个死前中断&#xff0c;可以用来作一个报警的功能。 独立看门狗超时时间计算公式 假设LSI是32KHz,超时时间等于 预分频系数&#xff08;4&…

平安科技(外包)面试分享

前言&#xff1a; 这是成都这边的平安科技面试分享&#xff0c;上家公司是做海外的&#xff0c;好不容易逮到公司离职赔偿的机会&#xff0c;我就离职了&#xff0c;没想到过了国庆节之后&#xff0c;工作是那么的难找&#xff0c;大概投了1-2周简历&#xff08;外包和短期项目…

Python 在PDF中绘制形状(线条、矩形、椭圆形等)

在PDF中绘制图形可以增强文档的视觉效果。通过添加不同类型的形状&#xff0c;如实线、虚线、矩形、圆形等&#xff0c;可以使文档更加生动有趣&#xff0c;提高读者的阅读兴趣。这对于制作报告、演示文稿或是教材特别有用。本文将通过以下几个示例介绍如何使用Python 在PDF中绘…

2-2.STM32之定时器TIM---输入捕获--实验2( PWMI模式测频率占空比)

输入捕获模式测频率、PWMI模式测频率占空比-CSDN博客 参考这篇文章&#xff01; 来利用一个GPIO的定时器的两个通道进行捕获占空比和频率&#xff0c;看出可以看出。TI1FP1和TI2FP2&#xff0c;计数值分别在CCR1和CCR2中取&#xff0c; 测周法 IC.c #include "stm32f1…

2024年转行指南:大学生进军就业前景广阔的领域——人工智能大模型

据教育部数据统计&#xff0c;2024高校毕业生规模预计达1179万人&#xff0c;将再创历史新高&#xff0c;“就业难”仍是当前大学毕业生需要直面的问题。在此背景下&#xff0c;选择一个就业前景好的专业尤为重要。 究竟学什么样的专业好就业呢&#xff1f;给毕业生们推荐3个当…

suanfabiji

1 差分练习 1 模板题 代码实现&#xff1a; import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int m sc.nextInt();int num sc.nextInt();long[][] arr new long[n 2][m 2…

WPS单元格重复值提示设置

选中要检查的所有的单元格 设置提示效果 当出现单元格值重复时&#xff0c;重复的单元格就会自动变化 要修改或删除&#xff0c;点击

一.Linux文件基本属性

前言&#xff1a;Linux系统是一个多用户系统&#xff0c;不同的用户处于不同的地位&#xff0c;也就是说具有不同的权限。为了安全&#xff0c;对于不同用户访问同一个文件&#xff0c;设置不同权限是很有必要的。 一.文件的基本属性理解 在Linux中&#xff0c;通常是这两个命…

【学习记录】使用CARLA录制双目摄像头SLAM数据

一、数据录制 数据录制的部分参考了网上的部分代码&#xff0c;代码本身并不复杂&#xff0c;基本都是简单的CARLA语法&#xff0c;关键的一点在于&#xff0c;CARLA内部本身并没有预设的双目摄像头&#xff0c;需要我们添加两个朝向相同的摄像头来组成双目系统&#xff0c;这…

算法的基础知识

算法的定义 算法是为了解决某类问题而规定的一个有限长的操作序列。 算法的特性 1. 有穷性&#xff08;Finiteness&#xff09; 含义&#xff1a;一个算法必须总是在执行有穷步后结束&#xff0c;且每一步都必须在有穷时间内完成。重要性&#xff1a;确保算法能够在合理的时…

城镇保障性住房管理:SpringBoot技术应用

2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统&#xff0c;它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等&#xff0c;非常…

【ComfyUI】flux人像摄影风格迁移的最优解?这个效果应该暂时无敌了吧?效果不好你打我!

大家好&#xff0c;这期我们主要讨论如何使用stable diffusion comfyUI 制作基于flux的人像摄影&#xff0c;主要实现风格迁移的功能。 我们都知道flux的生态目前不太完善&#xff0c;flux的controlnet和flux ipadapter虽然有&#xff0c;但效果不太好&#xff0c;可控性不强。…

基于微信的追星小程序+ssm(lw+演示+源码+运行)

摘 要 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;追星小程序被用户普遍使用&#xff0c;为方便用户能够可以…

esp32cam+Arduino IDE在编译时提示找不到 esp_camera.h 的解决办法

多半是因为你的ESP32库升级了&#xff0c;不再是 1.02版本&#xff0c;或者根本就没有 ESp32 库。如果被升级了&#xff0c;还原为1.02版本就可以了。如果没有&#xff0c;按照下述方法添加&#xff1a; 首先&#xff0c;在"文件"->"首选项"->"…

基于物联网设计的地下煤矿安全监测与预警

文章目录 一、前言1.1 项目介绍【1】项目开发背景【2】设计实现的功能【3】项目硬件模块组成 1.2 设计思路1.3 系统功能总结1.4 开发工具的选择【1】设备端开发【2】上位机开发 1.5 模块的技术详情介绍【1】NBIOT-BC26模块【2】MQ5传感器【4】DHT11传感器【5】红外热释电人体检…

第8章 利用CSS制作导航菜单作业

1.利用CSS技术&#xff0c;结合链接和列表&#xff0c;设计并实现“山水之间”页面。 浏览效果如下&#xff1a; HTML代码如下&#xff1a; <!DOCTYPE html> <html><head><meta charset"utf-8" /><title>山水之间</title><…

32单片机HAL库的引脚初始化

在使用HAL库时&#xff0c;GPIO初始化函数定义在stm32f4xx_hal_gpio.c文件中&#xff0c;如下&#xff1a; void HAL_GPIO_Init(GPIO_TypeDef *GPIOx, GPIO_InitTypeDef *GPIO_Init); 由这个函数可以看出&#xff0c;在初始化GPIO时&#xff0c;需要向函数传入2个结构体&…

Django安装

在终端创建django项目 1.查看自己的python版本 输入对应自己本机python的版本&#xff0c;列如我的是3.11.8 先再全局安装django依赖包 2.在控制窗口输入安装命令&#xff1a; pip3.11 install django 看到Successflully 说明我们就安装成功了 python的Scripts文件用于存…

网络层5——IPV6

目录 一、IPv6 vs IPv4 1、对IPv6主要变化 2、IPv4 vs IPv6 二、IPv6基本首部 1、版本——4位 2、通信量类——8位 3、流标号——20位 4、有效载荷长度——16位 5、下一个首部——8位 6、跳数限制——8位 7、源 、 目的地址——128位 8、扩展首部 三、IPv6地址 1…

怎么样鉴定疾病相关稀有细胞群?二值化精细模型标签,这个刚发的顶刊单细胞算法值得一学!

生信碱移 HiDDEN&#xff1a;抽丝剥茧 在具有病例和对照单细胞RNA测序研究中&#xff0c;样本级标签通常被直接赋予单个细胞&#xff0c;假设所有病例细胞都受影响。这种传统方法在受影响细胞比例较小或扰动强度较弱时&#xff0c;难以有效识别关键细胞及其标记基因&#xff…