C++のことばの梯子

2つの単語（beginWordとendWord）があり、辞書の単語リストがあるとします。beginWordからendWordまでの最短の変換シーケンスの長さを見つけます-

• 一度に変換できる文字は1つだけです。

• 変換された各単語は、単語リストに存在する必要があります。 beginWordは変換された単語ではありません。

そのことを覚えておく必要があります-

• そのような変更シーケンスがない場合は0を返します。

• すべての単語の長さは同じです。

• すべての単語には小文字のみが含まれます。

• 単語リストに重複はないと想定できます。

したがって、入力が次のようになっている場合：beginWord ="hit"、endWord ="cog"、wordlist =["hot"、 "dot"、 "dog"、 "lot"、 "log"、 "cog"]

次に、1つの最短変換がヒット→ホット→ドット→ドッグ→コグ

これを解決するには、次の手順に従います-

• putStarというメソッドを定義します。これにはjと文字列sが必要です。これは次のように機能します-

• temp：=空の文字列

• 0からsのサイズまでの範囲のiの場合– 1

  • i =jの場合は、「*」を連結してtempを更新します。それ以外の場合は、s[i]をtempと連結してtempを更新します。

• mainメソッドでは、文字列b、文字列e、および単語のリストwを取ります。これは、-

  のように機能します。

• eがwにない場合、bが空の場合、eが空の場合、またはwが空の場合は、0を返します

• 文字列型のキーと配列型の値のマップmを定義します。

• 0からwのサイズまでの範囲のiの場合

  • x：=w [i]

  • jの場合：=0からxのサイズ

    • inter：=putStar（j、x）

    • xをm[inter]

      に挿入します

• キューqを定義し、ペア（b、1）をqに挿入します

• 訪問済みと呼ばれる地図を作成する

• qが空ではない間

  • s：=qからフロントペア、qからフロント要素を削除

  • x：=ペアsの最初の要素、l：=ペアsの2番目の要素

  • 0からxのサイズまでの範囲のiの場合

    • temp：=putStar（i、x）

    • 0からm[temp]

      のサイズのjの場合

      • aa：=m [temp、j]

      • aaがeと同じ場合、l+1を返します

      • visited [aa]が設定されていない場合は、ペア（aa、l + 1）を挿入し、visited [aa] =1

        を設定します。

• レベル：=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