বর্ণানুক্রমিক ক্রম খুঁজুন যাতে শব্দগুলি C++-এ সাজানো বিবেচনা করা যেতে পারে

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

সুতরাং, যদি ইনপুট শব্দের মত হয় =["efgh", "wxyz"], তাহলে আউটপুট হবে zyxvutsrqponmlkjihgfewdcba

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

• বর্ণমালা :=২৬
• n :=v এর আকার
• যদি n 1 এর মত হয়, তাহলে −
  • "abcdefghijklmnopqrstuvwxyz" প্রদর্শন করুন
  • প্রত্যাবর্তন
• আলফাবেট আকারের একটি অ্যারে অ্যাডজ সংজ্ঞায়িত করুন
• আলফাবেটের আকারের একটি অ্যারে সংজ্ঞায়িত করুন এবং 0 দিয়ে পূরণ করুন
• প্রে :=v[0]
• আরম্ভ করার জন্য i :=1, যখন i করুন
• s :=v[i]
• 0 থেকে ন্যূনতম পরিসরে j-এর জন্য (পূর্বের আকার এবং s-এর আকার) - 1 −
  • যদি s[j] pre[j] এর সমান না হয়, তাহলে −
    • লুপ থেকে বেরিয়ে আসুন
  • যদি j
  • s[j] - adj[pre[j]-এর শেষে 'a'-এর ASCII - 'a'-এর ASCII যোগ করুন]
• এ [s[j] - ASCII of 'a'] 1 দ্বারা বৃদ্ধি
• প্রে :=s
• নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তিতে যান

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
#define ALPHABET 26
void search_ordering(vector<string> v) {
   int n = v.size();
   if (n == 1) {
      cout << "abcdefghijklmnopqrstuvwxyz";
      return;
   }
   vector<int> adj[ALPHABET];
   vector<int> in(ALPHABET, 0);
   string pre = v[0];
   for (int i = 1; i < n; ++i) {
      string s = v[i];
      int j;
      for (j = 0; j < min(pre.length(), s.length()); ++j)
         if (s[j] != pre[j])
            break;
      if (j < min(pre.length(), s.length())) {
         adj[pre[j] - 'a'].push_back(s[j] - 'a');
         in[s[j] - 'a']++;
         pre = s;
         continue;
      }
      if (pre.length() > s.length()) {
         cout << "Impossible";
         return;
      }
      pre = s;
   }
   stack<int> my_stack;
   for (int i = 0; i < ALPHABET; ++i)
      if (in[i] == 0)
         my_stack.push(i);
   vector<char> out;
   bool vis[26];
   memset(vis, false, sizeof(vis));
   while (!my_stack.empty()) {
      char x = my_stack.top();
      my_stack.pop();
      vis[x] = true;
      out.push_back(x + 'a');
      for (int i = 0; i < adj[x].size(); ++i) {
         if (vis[adj[x][i]])
            continue;
         in[adj[x][i]]--;
         if (in[adj[x][i]] == 0)
            my_stack.push(adj[x][i]);
      }
   }
   for (int i = 0; i < ALPHABET; ++i)
   if (!vis[i]) {
      cout << "Impossible";
      return;
   }
   for (int i = 0; i < out.size(); ++i)
   cout << out[i];
}
int main() {
   vector<string> v{"efgh", "wxyz"};
   search_ordering(v);
}

ইনপুট

{"efgh", "wxyz"}

আউটপুট

zyxvutsrqponmlkjihgfewdcba