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

输出示例

提示信息

从 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);
}
}
}
}