C++-এ ওয়ার্ড ল্যাডার

মনে করুন দুটি শব্দ (`beginWord` এবং `endWord`) আছে, এবং একটি ডিকশনারির শব্দের লিস্ট আছে, `beginWord` থেকে `endWord`-এ যেতে শর্টেস্ট ট্রান্সফরমেশন সিকোয়েন্সের দৈর্ঘ্য বের করতে হবে, যাতে -

একবারে শুধু একটি লেটার কনভার্ট করা যাবে।
প্রতিটি ট্রান্সফর্মড শব্দ ওয়ার্ড লিস্টে থাকতে হবে। `beginWord` একটি ট্রান্সফর্মড শব্দ নয়।

মনে রাখতে হবে যে -

যদি এমন কোনো ট্রান্সফরমেশন সিকোয়েন্স না থাকে, তবে ০ রিটার্ন করুন।
সব শব্দের দৈর্ঘ্য একই।
সব শব্দ শুধু लोওয়ারকেস ক্যারেক্টার ধারণ করে।
ওয়ার্ড লিস্টে ডুপ্লিকেট নেই এমন ধরে নেওয়া যেতে পারে।

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

তবে আউটপুট হবে ৫, কারণ একটি শর্টেস্ট ট্রান্সফরমেশন হলো hit → hot → dot → dog → cog

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -

`putStar` নামক একটি মেথড সংজ্ঞায়িত করুন, এটি `j` এবং স্ট্রিং `s` নেবে। এটি নিচের মোতাবিক কাজ করবে -
`temp :=` খালি স্ট্রিং
`i` = 0 থেকে `s`-এর আকার - 1 পর্যন্ত
- যদি `i = j`, তবে `temp`-কে `"*"` দিয়ে কনক্যাটেনেট করে আপডেট করুন, অন্যথায় `temp`-কে `s[i]` দিয়ে কনক্যাটেনেট করে আপডেট করুন।
মেইন মেথডে এটি স্ট্রিং `b`, স্ট্রিং `e` এবং শব্দের লিস্ট `w` নেবে, এটি নিচের মোতাবিক কাজ করবে -
যদি `e` `w`-এ না থাকে, অথবা `b` খালি, অথবা `e` খালি, অথবা `w` খালি, তবে ০ রিটার্ন করুন

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

`i` = 0 থেকে `w`-এর আকার পর্যন্ত
- `x := w[i]`
- `j` = 0 থেকে `x`-এর আকার
  - `inter := putStar(j, x)`
  - `x`-কে `m[inter]`-এ ইনসার্ট করুন
একটি কিউ `q` সংজ্ঞায়িত করুন, `(b, 1)` পেয়ারটি `q`-তে ইনসার্ট করুন
`visited` নামক একটি ম্যাপ তৈরি করুন
যখন `q` খালি না থাকে
- `s := q`-এর ফ্রন্ট পেয়ার, `q`-থেকে ফ্রন্ট এলিমেন্ট ডিলিট করুন
- `x := s`-এর ফাস্ট এলিমেন্ট, `l := s`-এর সেকেন্ড এলিমেন্ট
- `i` = 0 থেকে `x`-এর আকার
  - `temp := putStar(i, x)`
  - `j` = 0 থেকে `m[temp]`-এর আকার
    - `aa := m[temp][j]`
    - যদি `aa` `e`-এর সমান হয়, তবে `l + 1` রিটার্ন করুন
    - যদি `visited[aa]` সেট না থাকে, তবে `(aa, l + 1)` পেয়ার ইনসার্ট করুন, এবং `visited[aa] = 1` সেট করুন
`level := 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"]