卡码网 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;
}
}