C ++のことばの梯子（ターゲット単語に到達するための最短のチェーンの長さ）

この問題では、辞書と「start」と「target」の2つの単語が与えられます。私たちの仕事は、作業開始からターゲット単語までのチェーン（ラダー）を生成することです。チェーンは、各単語が他の文字と1単語だけ異なり、その単語も辞書に存在するように作成されます。対象の単語が辞書にあり、すべての単語の長さが同じです。プログラムは、開始からターゲットまでの最短パスの長さを返します。

問題を理解するために例を見てみましょう

入力

Dictionary = {‘HEAL’, ‘HATE’, ‘HEAT’, ‘TEAT’, ‘THAT’, ‘WHAT’ , ‘HAIL’ ‘THAE’}
Start = ‘HELL’
Target = ‘THAE’

出力

6

説明

HELL - HEAL - HEAT - TEAT - THAT - THAE

この問題を解決するために、辞書の幅優先探索を実行します。ここで、前の文字から1文字離れているすべての要素を段階的に見つけます。そして、最初からターゲットまではしごを作成します。

ソリューションの実装を示すプログラム

例

#include <bits/stdc++.h>
using namespace std;
int wordLadder(string start, string target, set<string>& dictionary) {
   if (dictionary.find(target) == dictionary.end())
   return 0;
   int level = 0, wordlength = start.size();
   queue<string> ladder;
   ladder.push(start);
   while (!ladder.empty()) {
      ++level;
      int sizeOfLadder = ladder.size();
      for (int i = 0; i < sizeOfLadder; ++i) {
         string word = ladder.front();
         ladder.pop();
         for (int pos = 0; pos < wordlength; ++pos) {
            char orig_char = word[pos];
            for (char c = 'a'; c <= 'z'; ++c) {
               word[pos] = c;
               if (word == target)
                  return level + 1;
               if (dictionary.find(word) == dictionary.end())
                  continue;
               dictionary.erase(word);
               ladder.push(word);
            }
            word[pos] = orig_char;
         }
      }
   }
   return 0;
}
int main() {
   set<string> dictionary;
   dictionary.insert("heal");
   dictionary.insert("heat");
   dictionary.insert("teat");
   dictionary.insert("that");
   dictionary.insert("what");
   dictionary.insert("thae");
   dictionary.insert("hlle");
   string start = "hell";
   string target = "thae";
   cout<<"Length of shortest chain from '"<<start<<"' to '"<<target<<"' is: "<<wordLadder(start, target, dictionary);
   return 0;
}

出力

Length of shortest chain from 'hell' to 'thae' is: 6