सी ++ में वर्ड लैडर

मान लीजिए कि हमारे पास दो शब्द हैं (beginWord और endWord), और हमारे पास शब्दकोष की शब्द सूची है, तो startWord से endWord तक के सबसे छोटे रूपांतरण अनुक्रम की लंबाई ज्ञात करें, जैसे -

एक बार में केवल एक अक्षर को बदला जा सकता है।
प्रत्येक रूपांतरित शब्द में शब्द सूची में मौजूद होना चाहिए। startWord एक रूपांतरित शब्द नहीं है।

हमें यह ध्यान रखना होगा कि -

जब ऐसा कोई परिवर्तन क्रम न हो तो वापस लौटें।
सभी शब्दों की लंबाई समान होती है।
सभी शब्दों में केवल लोअरकेस वर्ण होते हैं।
हम शब्द सूची में कोई डुप्लीकेट नहीं मान सकते हैं।

तो अगर इनपुट इस तरह है:startWord ="हिट", एंडवर्ड ="कोग", और वर्डलिस्ट =["हॉट", "डॉट", "डॉग", "लॉट", "लॉग", "कॉग"]

तब आउटपुट 5 होगा, क्योंकि एक सबसे छोटा परिवर्तन हिट होता है → हॉट → डॉट → डॉग → कोग

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

putStar नामक एक विधि को परिभाषित करें, इसमें j और string s लगेंगे। यह इस प्रकार काम करेगा -
अस्थायी:=खाली स्ट्रिंग
मैं के लिए 0 से लेकर s - 1 के आकार तक के लिए
- अगर मैं =जे, तो इसके साथ "*" को जोड़कर अस्थायी अद्यतन करें, अन्यथा अस्थायी के साथ एस [i] को जोड़कर अस्थायी अद्यतन करें।
मुख्य विधि में यह स्ट्रिंग बी, स्ट्रिंग ई और शब्दों की सूची लेगा, यह इस तरह काम करेगा -
अगर e w में नहीं है, या b खाली है, या e खाली है, या w खाली है, तो 0
लौटाएं
स्ट्रिंग प्रकार कुंजी और सरणी प्रकार मान के लिए मानचित्र m परिभाषित करें।
मेरे लिए 0 से w के आकार की सीमा में है
- एक्स:=डब्ल्यू[i]
- j के लिए:=0 से x के आकार तक
  - इंटर:=पुटस्टार (जे, एक्स)
  - x को m[inter]
    . में डालें
क्यू को परिभाषित करें, क्यू में एक जोड़ी (बी, 1) डालें
विज़िट नाम का नक्शा बनाएं
जबकि q खाली नहीं है
- s :=q से सामने की जोड़ी, q से सामने वाले तत्व को हटा दें
- x :=युग्म का प्रथम अवयव s, l :=युग्म s का दूसरा अवयव
- मेरे लिए 0 से x के आकार की सीमा में है
  - अस्थायी:=पुटस्टार(i, x)
  - j के लिए 0 से लेकर m[temp]
    के आकार तक की सीमा में
    - आ:=एम [अस्थायी, जे]
    - अगर एए ई के समान है, तो एल + 1 लौटाएं
    - अगर विज़िट किया गया [आ] सेट नहीं है, तो जोड़ी डालें (आ, एल + 1), और विज़िट किया गया सेट करें [आ] =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"]