मान लीजिए एक नई एलियन भाषा है जो लैटिन वर्णमाला का उपयोग करती है। हालांकि, अक्षरों के बीच का क्रम ज्ञात नहीं है। हमारे पास डिक्शनरी से गैर-खाली शब्दों की एक सूची है, ये शब्द इस नई भाषा के नियमों द्वारा लेक्सिकोग्राफिक रूप से सॉर्ट किए गए हैं। हमें इस भाषा में अक्षरों का क्रम ढूंढना है।
तो, यदि इनपुट ["wrt","wrf","er", "ett", "rftt" ] जैसा है, तो आउटपुट "wertf" होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
degree नामक एक मैप परिभाषित करें
graph नामक एक मैप परिभाषित करें
n := words का आकार
i := 0 से आरंभ करें, जब i, words के आकार से कम, अद्यतन करें (i को 1 से बढ़ाएं), करें −
j := 0 से आरंभ करें, जब j, words[i] के आकार से कम, अद्यतन करें (j को 1 से बढ़ाएं), करें −
degree[words[i, j]] := 0
i := 0 से आरंभ करें, जब i < n - 1, अद्यतन करें (i को 1 से बढ़ाएं), करें −
l := words[i] के आकार और words[i + 1] के आकार का न्यूनतम
j := 0 से आरंभ करें, जब j < l, अद्यतन करें (j को 1 से बढ़ाएं), करें −
x := words[i, j]
y := words[i + 1, j]
यदि x, y के बराबर नहीं है, तो −
y को graph[x] के अंत में डालें
(degree[y] को 1 से बढ़ाएं)
लूप से बाहर आएं
ret := खाली स्ट्रिंग
एक कतार q परिभाषित करें
degree में प्रत्येक कुंजी-मान जोड़ी it के लिए, करें −
यदि it का मान 0 के समान है, तो −
it की कुंजी को q में डालें
जब तक (q खाली नहीं है), करें −
x := q का पहला तत्व
q से तत्व हटाएं
ret := ret + x
graph में प्रत्येक तत्व sit के लिए करें −
degree[sit] को 1 से घटाएं
यदि degree[sit] 0 के समान है, तो −
sit को q में डालें
(sit को 1 से बढ़ाएं)
लौटाएं (यदि ret का आकार degree के आकार के समान है, तो ret, अन्यथा खाली स्ट्रिंग)
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
#include <bits/stdc++.h> using namespace std; class Solution { public: string alienOrder(vector<string>& words) { map<char, int> degree; map<char, vector<char> > graph; int n = words.size(); for (int i = 0; i < words.size(); i++) { for (int j = 0; j < words[i].size(); j++) { degree[words[i][j]] = 0; } } for (int i = 0; i < n - 1; i++) { int l = min((int)words[i].size(), (int)words[i + 1].size()); for (int j = 0; j < l; j++) { char x = words[i][j]; char y = words[i + 1][j]; if (x != y) { graph[x].push_back(y); degree[y]++; break; } } } string ret = ""; queue<char> q; map<char, int>::iterator it = degree.begin(); while (it != degree.end()) { if (it->second == 0) { q.push(it->first); } it++; } while (!q.empty()) { char x = q.front(); q.pop(); ret += x; vector<char>::iterator sit = graph[x].begin(); while (sit != graph[x].end()) { degree[*sit]--; if (degree[*sit] == 0) { q.push(*sit); } sit++; } } return ret.size() == degree.size() ? ret : ""; } }; main(){ Solution ob; vector<string> v = {"wrt","wrf","er","ett","rftt"}; cout <<(ob.alienOrder(v)); }इनपुट
{"wrt","wrf","er","ett","rftt"}आउटपुट
wertf
