मान लीजिए हमारे पास शब्दों की एक सरणी है, हमें अंग्रेजी वर्णमाला में कोई वर्णमाला क्रम ढूंढना है ताकि दिए गए शब्दों को आरोही क्रम में सॉर्टेड माना जा सके, यदि ऐसा कोई क्रम मौजूद है, अन्यथा "impossible" लौटाएं।
तो, यदि इनपुट words = ["efgh", "wxyz"] जैसा है, तो आउटपुट zyxvutsrqponmlkjihgfewdcba होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
<उल क्लास="सूची"><ली>ALPHABET := 26<ली>n := v का आकार<ली>यदि n 1 के समान है, तो −<उल क्लास="सूची"><ली>"abcdefghijklmnopqrstuvwxyz" प्रदर्शित करें<ली>लौटें<ली>ALPHABET आकार का एक सरणी adj परिभाषित करें<ली>ALPHABET आकार का एक सरणी in परिभाषित करें और 0 से भरें<ली>pre := v[0]<ली>i := 1 से इनिशियलाइज़ करें, जब i < n, अपडेट करें (i को 1 से बढ़ाएं), तब तक करें −<उल क्लास="सूची"><ली>s := v[i]<ली>j को 0 से minimum of (pre का आकार और s का आकार) - 1 तक की रेंज में −<उल क्लास="सूची"><ली>यदि s[j], pre[j] के बराबर नहीं है, तो −<उल क्लास="सूची"><ली>लूप से बाहर आएं<ली>यदि j < pre के आकार और s के आकार के न्यूनतम के बराबर है, तो −<उल क्लास="सूची"><ली>s[j] - 'a' का ASCII को adj[pre[j] - 'a' का ASCII] के अंत में डालें<ली>in[s[j] - 'a' का ASCII] को 1 से बढ़ाएं<ली>pre := s<ली>निम्नलिखित भाग को अनदेखा करें, अगली पुनरावृत्ति पर जाएं<ली>यदि pre का आकार > s का आकार, तो −<उल क्लास="सूची"><ली>"Impossible" प्रदर्शित करें<ली>लौटें<ली>pre := s<ली>एक स्टैक my_stack परिभाषित करें<ली>i := 0 से इनिशियलाइज़ करें, जब i < ALPHABET, अपडेट करें (i को 1 से बढ़ाएं), तब तक करें −<उल क्लास="सूची"><ली>यदि in[i] 0 के समान है, तो −<उल क्लास="सूची"><ली>i को my_stack में डालें<ली>out नामक एक सरणी परिभाषित करें<ली>26 आकार का एक सरणी vis परिभाषित करें। false से भरें<ली>जब तक (my_stack खाली नहीं है), तब तक करें −<उल क्लास="सूची"><ली>x := my_stack का शीर्ष तत्व<ली>my_stack से तत्व हटाएं<ली>vis[x] := true<ली>x + 'a' का ASCII को out के अंत में डालें<ली>i := 0 से इनिशियलाइज़ करें, जब i < adj[x] का आकार, अपडेट करें (i को 1 से बढ़ाएं), तब तक करें −<उल क्लास="सूची"><ली>यदि vis[adj[x, i]] शून्येतर है, तो −<उल क्लास="सूची"><ली>निम्नलिखित भाग को अनदेखा करें, अगली पुनरावृत्ति पर जाएं<ली>(in[adj[x, i]] को 1 से घटाएं)<ली>यदि in[adj[x, i]] 0 के समान है, तो −<उल क्लास="सूची"><ली>adj[x, i] को my_stack में डालें<ली>i := 0 से इनिशियलाइज़ करें, जब i < ALPHABET, अपडेट करें (i को 1 से बढ़ाएं), तब तक करें −<उल क्लास="सूची"><ली>यदि not vis[i] शून्येतर है, तो −<उल क्लास="सूची"><ली>"Impossible" प्रदर्शित करें<ली>लौटें<ली>i := 0 से इनिशियलाइज़ करें, जब i < out का आकार, अपडेट करें (i को 1 से बढ़ाएं), तब तक करें −<उल क्लास="सूची"><ली>out[i] प्रदर्शित करेंउदाहरण
बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें −
<प्रि क्लास="प्रिटीप्रिंट नोट्रांसलेट">#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
