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