C++ এ ওয়ার্ড ল্যাডার (লক্ষ্যের শব্দে পৌঁছানোর জন্য সবচেয়ে ছোট চেইনের দৈর্ঘ্য)

এই সমস্যায়, আমাদের একটি অভিধান এবং দুটি শব্দ 'শুরু' এবং 'লক্ষ্য' দেওয়া হয়েছে। আমাদের কাজ হল শুরুর কাজ থেকে লক্ষ্য শব্দ পর্যন্ত একটি চেইন (মই) তৈরি করা, চেইনটি এমনভাবে তৈরি করা হয়েছে যে প্রতিটি শব্দ অন্য অক্ষরকে শুধুমাত্র একটি শব্দ দ্বারা পৃথক করে এবং শব্দটি অভিধানে থাকা উচিত। লক্ষ্য শব্দটি অভিধানে বিদ্যমান এবং সমস্ত শব্দের দৈর্ঘ্য একই। প্রোগ্রামটি শুরু থেকে লক্ষ্য পর্যন্ত সংক্ষিপ্ততম পথের দৈর্ঘ্য ফিরিয়ে দেবে।

সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,

ইনপুট

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

আউটপুট

6

ব্যাখ্যা

HELL - HEAL - HEAT - TEAT - THAT - THAE

এই সমস্যা সমাধানের জন্য, আমরা ডিকশনারির ব্রেডথ-ফার্স্ট সার্চ করব। এখন, ধাপে ধাপে আগের অক্ষর থেকে এক অক্ষর দূরে থাকা সমস্ত উপাদান খুঁজুন। এবং শুরু থেকে লক্ষ্য পর্যন্ত একটি মই তৈরি করুন৷

আমাদের সমাধানের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম,

উদাহরণ

#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