सी ++ में वर्ड लैडर (लक्षित शब्द तक पहुंचने के लिए सबसे छोटी श्रृंखला की लंबाई)

इस समस्या में हमें एक शब्दकोष और दो शब्द 'स्टार्ट' और 'टारगेट' दिए गए हैं। हमारा काम काम शुरू करने से लेकर लक्ष्य शब्द तक एक श्रृंखला (सीढ़ी) उत्पन्न करना है, श्रृंखला इस तरह बनाई जाती है कि प्रत्येक शब्द दूसरे वर्ण को केवल एक शब्द से अलग करता है और शब्द भी शब्दकोश में मौजूद होना चाहिए। लक्ष्य शब्द शब्दकोश में मौजूद है और सभी शब्दों की लंबाई भी समान है। कार्यक्रम शुरू से लक्ष्य तक सबसे छोटे पथ की लंबाई लौटाएगा।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

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

आउटपुट

6

स्पष्टीकरण

HELL - HEAL - HEAT - TEAT - THAT - THAE

इस समस्या को हल करने के लिए, हम शब्दकोश की Breadth-first search करेंगे। अब, चरण दर चरण उन सभी तत्वों को खोजें जो पिछले वर्ण से एक अक्षर की दूरी पर हों। और शुरू से लक्ष्य तक एक सीढ़ी बनाएं।

हमारे समाधान के कार्यान्वयन को दिखाने के लिए कार्यक्रम,

उदाहरण

#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