C++ 词梯


假设我们有两个单词(beginWord 和 endWord),以及词典的单词列表,找出从 beginWord 到 endWord 的最短转换序列的长度,条件是:

  • 每次只能转换一个字母。

  • 每个转换后的单词必须存在于单词列表中。beginWord 不是转换后的单词。

我们需要记住:

  • 如果没有这样的转换序列,则返回 0。

  • 所有单词长度相同。

  • 所有单词仅包含小写字母。

  • 我们可以假设单词列表中没有重复。

因此,如果输入如下:beginWord = "hit",endWord = "cog",wordlist = ["hot", "dot", "dog", "lot", "log", "cog"]

则输出将为 5,因为其中一个最短的转换是 hit → hot → dot → dog → cog

为了解决这个问题,我们将遵循以下步骤:

  • 定义一个名为 putStar 的方法,它将接收 j 和字符串 s。其工作原理如下:

  • temp := 空字符串

  • 对于 i 的范围为 0 到 s 的大小 – 1

    • 如果 i = j,则通过将“*”与它连接来更新 temp,否则通过将 s[i] 与 temp 连接来更新 temp。

  • 在主方法中,它将接收字符串 b、字符串 e 和单词列表 w,其工作方式如下:

  • 如果 e 不在 w 中,或者 b 为空,或者 e 为空,或者 w 为空,则返回 0

  • 为字符串类型键和数组类型值定义一个映射 m。

  • 对于 i 的范围为 0 到 w 的大小

    • x := w[i]

    • 对于 j := 0 到 x 的大小

      • inter := putStar(j, x)

      • 将 x 插入 m[inter]

  • 定义一个队列 q,将一个对 (b, 1) 插入 q

  • 创建一个名为 visited 的映射

  • 当 q 不为空时

    • s := 来自 q 的前面一对,从 q 中删除前面元素

    • x := 对 s 的第一个元素,l := 对 s 的第二个元素

    • 对于 i 的范围为 0 到 x 的大小

      • temp := putStar(i, x)

      • 对于 j 的范围为 0 到 m[temp] 的大小

        • aa := m[temp, j]

        • 如果 aa 与 e 相同,则返回 l + 1

        • 如果未设置 visited[aa],则插入对 (aa, l + 1),并设置 visited[aa] = 1

  • level := 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

更新于:2020年4月29日

752 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告