C++ এ শব্দ মই

ধরুন আমাদের কাছে দুটি শব্দ (beginWord এবং endWord) আছে, এবং আমাদের কাছে অভিধানের শব্দ তালিকা আছে, বিগিনওয়ার্ড থেকে এন্ডওয়ার্ড পর্যন্ত সংক্ষিপ্ততম রূপান্তর অনুক্রমের দৈর্ঘ্য খুঁজে বের করুন, যেমন −

• একটি সময়ে শুধুমাত্র একটি অক্ষর রূপান্তর করা যেতে পারে৷

  ৷

• প্রতিটি রূপান্তরিত শব্দ শব্দ তালিকায় বিদ্যমান থাকা আবশ্যক. beginWord একটি রূপান্তরিত শব্দ নয়।

আমাদের মনে রাখতে হবে যে −

• 0 রিটার্ন করুন যখন এই ধরনের কোন পরিবর্তন ক্রম নেই।

• সব শব্দের দৈর্ঘ্য একই।

• সমস্ত শব্দে শুধুমাত্র ছোট হাতের অক্ষর থাকে৷

• আমরা শব্দ তালিকায় কোন সদৃশ অনুমান করতে পারি।

তাই যদি ইনপুট হয়:beginWord ="hit", endWord ="cog", এবং wordlist =["hot", "dot", "dog", "lot", "log", "cog"]

তারপর আউটপুট হবে 5, কারণ একটি সংক্ষিপ্ত রূপান্তর → হট → ডট → ডগ → কগ

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• পুটস্টার নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি j এবং স্ট্রিং s নেবে। এটি নিম্নরূপ কাজ করবে -

• temp :=খালি স্ট্রিং

• 0 থেকে s - 1

  এর আকারের মধ্যে i এর জন্য

  • যদি i =j হয়, তাহলে এটির সাথে "*" সংযুক্ত করে temp আপডেট করুন, অন্যথায় s[i] কে temp এর সাথে সংযুক্ত করে temp আপডেট করুন।

• মূল পদ্ধতিতে স্ট্রিং b, স্ট্রিং ই এবং শব্দের তালিকা w লাগবে, এটি −

  এর মত কাজ করবে

• যদি w-তে e না থাকে, বা b খালি হয়, বা e খালি হয়, বা w খালি হয়, তাহলে 0 ফেরত দিন

• স্ট্রিং টাইপ কী এবং অ্যারে টাইপ মানের জন্য একটি মানচিত্র m সংজ্ঞায়িত করুন।

• আমি 0 থেকে w

  এর পরিসরে

  • x :=w[i]

  • j এর জন্য :=0 থেকে x এর আকার

    • inter :=putStar(j, x)

    • m[ইন্টার]

      -এ x ঢোকান

• একটি সারি q সংজ্ঞায়িত করুন, q

  এ একটি জোড়া (b, 1) সন্নিবেশ করুন

• ভিজিটড

  নামে একটি মানচিত্র তৈরি করুন

• যখন q খালি নয়

  • s :=q থেকে ফ্রন্ট পেয়ার, q থেকে ফ্রন্ট এলিমেন্ট মুছে দিন

  • x :=জোড়ার প্রথম উপাদান s, l :=জোড়ার দ্বিতীয় উপাদান s

  • আমি 0 থেকে x এর আকারের মধ্যে

    • temp :=putStar(i, x)

    • j এর জন্য রেঞ্জ 0 থেকে m[temp]

      • aa :=m[temp, j]

      • aa যদি e এর মত হয়, তাহলে l + 1

        ফেরত দিন

      • যদি পরিদর্শন করা [aa] সেট করা না থাকে, তাহলে জোড়া (aa, l + 1) ঢোকান এবং পরিদর্শন করা [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