वर्णानुक्रम का पता लगाएं जैसे कि शब्दों को C++ में क्रमबद्ध माना जा सकता है

मान लीजिए कि हमारे पास शब्दों की एक सरणी है, हमें अंग्रेजी वर्णमाला में कोई वर्णानुक्रमिक क्रम खोजना है ताकि दिए गए शब्दों को आरोही क्रम में क्रमबद्ध माना जा सके, यदि ऐसा कोई क्रम मौजूद है, अन्यथा "असंभव" लौटाएं।

इसलिए, यदि इनपुट शब्द =["efgh", "wxyz"] जैसा है, तो आउटपुट zyxvutsrqponmlkjihgfewdcba

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

• वर्णमाला:=26
• n :=v का आकार
• यदि n 1 के समान है, तो −
  • प्रदर्शन "abcdefghijklmnopqrstuvwxyz"
  • वापसी
• एक सरणी adj को आकार ALPHABET परिभाषित करें
• किसी सरणी को ALPHABET आकार में परिभाषित करें और 0 से भरें
• पूर्व:=v[0]
• इनिशियलाइज़ i :=1 के लिए, जब i करें
• s :=v[i]
• जे के लिए 0 से न्यूनतम (पूर्व का आकार और आकार का आकार) - 1 -
  • यदि s[j] पूर्व[j] के बराबर नहीं है, तो −
    • लूप से बाहर आएं
  • यदि j <पूर्व के आकार का न्यूनतम और s का आकार, तो −
    • सम्मिलित करें [j] - adj के अंत में 'a' का ASCII [pre[j] - 'a' का ASCII]
  • [s[j] - 'a'] के ASCII में 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