एलियन डिक्शनरी इन सी++

मान लीजिए कि एक नई विदेशी भाषा है और वह लैटिन वर्णमाला का उपयोग करती है। हालांकि, अक्षरों के बीच का क्रम ज्ञात नहीं है। हमारे पास शब्दकोश से गैर-रिक्त शब्दों की एक सूची है, इन शब्दों को इस नई भाषा के नियमों द्वारा शब्दावली के अनुसार क्रमबद्ध किया गया है। हमें इस भाषा में अक्षरों का क्रम खोजना होगा।

इसलिए, यदि इनपुट ["wrt",,"wrf",,"er", "ett", "rftt" ] जैसा है, तो आउटपुट "wertf"

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

• डिग्री नामक एक मानचित्र परिभाषित करें

• ग्राफ़ नामक एक मानचित्र परिभाषित करें

• n :=शब्दों का आकार

• इनिशियलाइज़ i :=0 के लिए, जब i <शब्दों का आकार, अपडेट (i 1 से बढ़ाएँ), करें -

  • इनिशियलाइज़ j :=0 के लिए, जब j <शब्दों का आकार [i], अपडेट करें (1 से j बढ़ाएँ), करें -

    • डिग्री [शब्द [i, j]]:=0

• इनिशियलाइज़ i :=0 के लिए, जब i

  • l :=शब्दों का न्यूनतम आकार [i] और शब्दों का आकार [i + 1]

  • इनिशियलाइज़ j :=0 के लिए, जब j

    • x:=शब्द[i, j]

    • y:=शब्द[i + 1, j]

    • यदि x, y के बराबर नहीं है, तो -

      • ग्राफ़ के अंत में y डालें[x]

      • (डिग्री [y] 1 से बढ़ाएं)

      • लूप से बाहर आएं

• रिट:=खाली स्ट्रिंग

• एक कतार को परिभाषित करें q

• प्रत्येक की-वैल्यू पेयर के लिए इसे डिग्री में करें −

  • यदि इसका मान 0 के समान है, तो -

    • q में इसकी कुंजी डालें

• जबकि (नहीं q खाली है), करें -

  • x :=q का पहला तत्व

  • q से तत्व हटाएं

  • रिट:=रिट + एक्स

  • प्रत्येक तत्व के लिए ग्राफ में बैठें -

    • डिग्री कम करें[बैठें] 1

    • अगर डिग्री [सीट] 0 के समान है, तो -

      • q में सिट डालें

    • (बैठक को 1 से बढ़ाएं)

• वापसी (यदि रिट का आकार डिग्री के आकार के समान है, तो रिट, अन्यथा रिक्त स्ट्रिंग)

उदाहरण

आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -

#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