C++ এ এলিয়েন অভিধান

ধরুন একটি নতুন এলিয়েন ভাষা আছে এবং সেটি ল্যাটিন বর্ণমালা ব্যবহার করে। যাইহোক, চিঠির মধ্যে আদেশ জানা যায়নি. আমাদের কাছে অভিধান থেকে অ-খালি শব্দগুলির একটি তালিকা রয়েছে, এই শব্দগুলি এই নতুন ভাষার নিয়ম অনুসারে অভিধানিকভাবে সাজানো হয়েছে। আমাদের এই ভাষার অক্ষরের ক্রম খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি ["wrt","wrf","er", "ett", "rftt" ] এর মত হয়, তাহলে আউটপুট হবে "wertf"

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• ডিগ্রি নামে একটি মানচিত্র সংজ্ঞায়িত করুন

• গ্রাফ নামে একটি মানচিত্র সংজ্ঞায়িত করুন

• n :=শব্দের আকার

• আরম্ভ করার জন্য i :=0, যখন i <শব্দের আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −

  • j শুরু করার জন্য :=0, যখন j <শব্দের আকার[i], আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), করুন −

    • ডিগ্রি[শব্দ[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 দ্বারা বৃদ্ধি করুন)

      • লুপ থেকে বেরিয়ে আসুন

• ret :=ফাঁকা স্ট্রিং

• একটি সারি q

  সংজ্ঞায়িত করুন

• প্রতিটি কী-মানের জন্য এটিকে ডিগ্রীতে যুক্ত করুন, −

  করুন

  • যদি এর মান 0 এর সমান হয়, তাহলে −

    • q

      -এ এটির কী সন্নিবেশ করান

• যখন (q খালি নয়), −

  করুন

  • x :=q

    এর প্রথম উপাদান

  • q

    থেকে উপাদান মুছুন

  • ret :=ret + x

  • প্রতিটি উপাদানের জন্য গ্রাফে বসুন −

    • ডিগ্রী [বসে] 1 দ্বারা হ্রাস করুন

    • যদি ডিগ্রি [sit] 0 এর সমান হয়, তাহলে −

      • q

        -এ বসুন

    • (সিট 1 দ্বারা বাড়ান)

• রিটার্ন (যদি রেটের আকার ডিগ্রীর আকারের সমান হয়, তাহলে 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