C ++中的字梯
假设我们有两个单词（beginWord和endWord），并且我们有字典的单词列表，找到从beginWord到endWord的最短转换序列的长度，例如-
一次只能转换一个字母。
在每个转换的单词中，单词列表中都必须存在。beginWord不是转换后的单词。
我们必须记住-
如果没有这样的更改序列，则返回0。
所有单词的长度相同。
所有单词仅包含小写字符。
我们可以假设单词列表中没有重复项。
因此，如果输入类似于：beginWord=“hit”，endWord=“cog”和wordlist=[“hot”，“dot”，“dog”，“lot”，“log”，“cog”]
然后输出为5，因为命中了最短的变换→热→点→狗→齿轮
为了解决这个问题，我们将遵循以下步骤-
定义一个名为putStar的方法，它将使用j和string。这将如下工作-
temp：=空字符串
当我的范围是0到s的大小–1
如果i=j，则通过将“*”串联来更新温度，否则将s[i]与温度串联来更新温度。
在main方法中，它将采用字符串b，字符串e和单词列表w，这将类似于-
如果e不在w中，或者b为空，或者e为空，或者w为空，则返回0
为字符串类型键和数组类型值定义映射m。
对于范围0到w的i
内部：=putStar(j,x)
将x插入m[inter]
x：=w[i]
对于j：=0到x的大小
定义队列q，在q中插入一对(b,1)
制作一张称为访问过的映射
当q不为空时
temp：=putStar(i,x)
对于范围从0到m[temp]的j
aa：=m[temp，j]
如果aa与e相同，则返回l+1
如果未设置Visited[aa]，则插入对（aa，l+1），并设置Visited[aa]=1
s：=q中的前对，从q中删除前元素
x：=对s的第一个元素，l：=对s的第二个元素
对于0到x范围内的i
等级：=0
返回0
示例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string putStar(int j, string s){
string temp = "";
for(int i = 0; i < s.size(); i++){
if(i == j)temp += "*";
else temp += s[i];
}
return temp;
}
int ladderLength(string b, string e, vector<string>& w) {
if(find(w.begin(), w.end(), e) == w.end() || !b.size() || !e.size() || !w.size())return 0;
map < string , vector <string> > m;
for(int i = 0; i < w.size(); i++){
string x = w[i];
for(int j = 0; j < x.size(); j++){
string inter = putStar(j,x);
m[inter].push_back(x);
}
}
queue < pair <string, int> > q;
q.push({b, 1});
map <string, int> visited;
while(!q.empty()){
pair < string, int > s = q.front();
q.pop();
string x = s.first;
int l = s.second;
for(int i = 0; i < x.size(); i++){
string temp = putStar(i ,x);
for(int j = 0; j < m[temp].size(); j++){
string aa = m[temp][j];
if(aa == e)return l+1;
if(!visited[aa]){
q.push({aa, l+1});
visited[aa] = 1;
}
}
}
}
int level = 0;
return 0;
}
};
main(){
vector<string> v = {"hot","dot","dog","lot","log","cog"};
Solution ob;
cout << (ob.ladderLength("hit", "cog", v));
}输入值
"hit" "cog" ["hot","dot","dog","lot","log","cog"]
输出结果
5