मान लीजिए हमारे पास दो शब्द (beginWord और endWord) हैं, और हमारे पास डिक्शनरी की वर्ड लिस्ट है, beginWord से endWord तक सबसे छोटे ट्रांसफॉर्मेशन सीक्वेंस की लंबाई ढूंढें, जैसे कि -
- एक समय में केवल एक अक्षर बदला जा सकता है।
- प्रत्येक ट्रांसफॉर्म्ड वर्ड वर्ड लिस्ट में मौजूद होना चाहिए। beginWord एक ट्रांसफॉर्म्ड वर्ड नहीं है।
हमें ध्यान रखना होगा कि -
- जब ऐसा कोई चेंज सीक्वेंस नहीं है तो 0 लौटाएं।
- सभी शब्दों की लंबाई समान होती है।
- सभी शब्दों में केवल लोअरकेस वर्ण होते हैं।
- हम मान सकते हैं कि वर्ड लिस्ट में कोई डुप्लिकेट नहीं है।
यदि इनपुट इस प्रकार है: beginWord = "hit", endWord = "cog", और wordlist = ["hot", "dot", "dog", "lot", "log", "cog"]
तो आउटपुट 5 होगा, क्योंकि एक सबसे छोटा ट्रांसफॉर्मेशन है hit → hot → dot → dog → cog
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- putStar नामक एक मेथड परिभाषित करें, यह j और स्ट्रिंग s लेगा। यह निम्नानुसार काम करेगा -
- टेम्प := खाली स्ट्रिंग
- i के लिए 0 से s के आकार - 1 तक की रेंज में
- यदि i = j है, तो टेम्प को इसके साथ "*" जोड़कर अपडेट करें, अन्यथा टेम्प को s[i] के साथ जोड़कर अपडेट करें।
- मेन मेथड में यह स्ट्रिंग b, स्ट्रिंग e और वर्ड्स की लिस्ट w लेगा, यह निम्नानुसार काम करेगा -
- यदि e w में नहीं है, या b खाली है, या e खाली है, या w खाली है, तो 0 लौटाएं
- स्ट्रिंग टाइप की और ऐरे टाइप वैल्यू के मैप m को परिभाषित करें।
- i के लिए 0 से w के आकार तक की रेंज में
- x := w[i]
- j := 0 से x के आकार तक
- इंटर := putStar(j, x)
- x को m[इंटर] में डालें
- एक क्यू q परिभाषित करें, q में पेयर (b, 1) डालें
- विजिटेड नामक एक मैप बनाएं
- जब तक q खाली नहीं है
- s := q से फ्रंट पेयर, q से फ्रंट एलिमेंट डिलीट करें
- x := पेयर s का फर्स्ट एलिमेंट, l := पेयर s का सेकंड एलिमेंट
- i के लिए 0 से x के आकार तक की रेंज में
- टेम्प := putStar(i, x)
- j के लिए 0 से m[टेम्प] के आकार तक की रेंज में
- aa := m[टेम्प, 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
