按字母顺序排列，这样就可以认为单词已排序-yiteyi-C++库

给定一个单词数组，在英语字母表中找到任何字母顺序，这样给定的单词就可以被认为是排序的（递增的），如果存在这样的顺序，否则就不可能输出。

null

例如：

Input :  words[] = {"zy", "ab"}
Output : zabcdefghijklmnopqrstuvwxy
Basically we need to make sure that 'z' comes
before 'a'.

Input :  words[] = {"geeks", "gamers", "coders", 
                    "everyoneelse"}
Output : zyxwvutsrqponmlkjihgceafdb

Input : words[] = {"marvel", "superman", "spiderman", 
                                           "batman"
Output : zyxwvuptrqonmsbdlkjihgfeca

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

天真的方法： 蛮力方法将检查所有可能的顺序，并检查其中是否有任何一个符合给定的单词顺序。考虑到有 26 英文字母表中有 26! 可以是有效顺序的排列数。考虑到我们检查每一对来验证一个订单，这种方法的复杂性会增加到 O（26！*N^2） ，这远远超出了人们所喜欢的时间复杂度。

使用拓扑排序： 这个解决方案需要了解图及其邻接表表示 , DFS 和拓扑排序 .

在我们要求的顺序中，要求打印字母，以便每个字母后面必须有优先级低于它们的字母。这似乎有点像拓扑排序定义为–在拓扑排序中，我们需要在相邻顶点之前打印一个顶点。让我们将字母表中的每个字母定义为标准有向图中的节点。 A. 据说与 B （A->B）如果 A. 先于 B 按顺序。该算法的公式如下：

如果 N 是 1. ，则任何订单均有效。
以前两个词为例。识别单词中的第一个不同字母（在单词的同一索引处）。第一个单词中的字母将位于第二个单词中的字母之前。
如果不存在这样的字母，那么第一个字符串的长度必须小于第二个字符串。
将第二个单词赋给第一个单词，并将第三个单词输入第二个单词。重复 2. , 3. 和 4. （n-1） 时报。
运行一个 DFS 按拓扑顺序遍历。
检查是否访问了所有节点。按照拓扑顺序，如果图中存在循环，则循环中的节点保持未访问状态，因为在访问与其相邻的每个节点后，不可能访问这些节点。在这种情况下，秩序并不存在。在这种情况下，这意味着我们列表中的顺序自相矛盾。

                     /* CPP program to find an order of alphabets                   
                     so that given set of words are considered                   
                     sorted */                   
                     #include <bits/stdc++.h>                   
                     using                               namespace                               std;                   
                     #define MAX_CHAR 26                   
                             
                     void                               findOrder(vector<string> v)                   
                     {                   
                                         int                               n = v.size();                   
                             
                                         /* If n is 1, then any order works */                   
                                         if                               (n == 1) {                   
                                         cout <<                               "abcdefghijklmnopqrstuvwxyz"                               ;                   
                                         return                               ;                   
                                         }                   
                             
                                         /* Adjacency list of 26 characters*/                   
                                         vector<                               int                               > adj[MAX_CHAR];                   
                             
                                         /* Array tracking the number of edges that are                   
                                         inward to each node*/                   
                                         vector<                               int                               > in(MAX_CHAR, 0);                   
                             
                                         // Traverse through all words in given array                   
                                         string prev = v[0];                   
                             
                                         /* (n-1) loops because we already acquired the                   
                                         first word in the list*/                   
                                         for                               (                               int                               i = 1; i < n; ++i) {                   
                                         string s = v[i];                   
                             
                                         /* Find first such letter in the present string that is different                   
                                         from the letter in the previous string at the same index*/                   
                                         int                               j;                   
                                         for                               (j = 0; j < min(prev.length(), s.length()); ++j)                   
                                         if                               (s[j] != prev[j])                   
                                         break                               ;                   
                             
                                         if                               (j < min(prev.length(), s.length())) {                   
                             
                                         /* The letter in the previous string precedes the one                   
                                         in the present string, hence add the letter in the present                   
                                         string as the child of the letter in the previous string*/                   
                                         adj[prev[j] -                               'a'                               ].push_back(s[j] -                               'a'                               );                   
                             
                                         /* The number of inward pointing edges to the node representing                   
                                         the letter in the present string increases by one*/                   
                                         in[s[j] -                               'a'                               ]++;                   
                             
                                         /* Assign present string to previous string for the next                   
                                         iteration. */                   
                                         prev = s;                   
                                         continue                               ;                   
                                         }                   
                             
                                         /* If there exists no such letter then the string length of                   
                                         the previous string must be less than or equal to the                   
                                         present string, otherwise no such order exists*/                   
                                         if                               (prev.length() > s.length()) {                   
                                         cout <<                               "Impossible"                               ;                   
                                         return                               ;                   
                                         }                   
                             
                                         /* Assign present string to previous string for the next                   
                                         iteration */                   
                                         prev = s;                   
                                         }                   
                             
                                         /* Topological ordering requires the source nodes                   
                                         that have no parent nodes*/                   
                                         stack<                               int                               > stk;                   
                                         for                               (                               int                               i = 0; i < MAX_CHAR; ++i)                   
                                         if                               (in[i] == 0)                   
                                         stk.push(i);                   
                             
                                         /* Vector storing required order (anyone that satisfies) */                   
                                         vector<                               char                               > out;                   
                             
                                         /* Array to keep track of visited nodes */                   
                                         bool                               vis[26];                   
                                         memset                               (vis,                               false                               ,                               sizeof                               (vis));                   
                             
                                         /* Standard DFS */                   
                                         while                               (!stk.empty()) {                   
                             
                                         /* Acquire present character */                   
                                         char                               x = stk.top();                   
                                         stk.pop();                   
                             
                                         /* Mark as visited */                   
                                         vis[x] =                               true                               ;                   
                             
                                         /* Insert character to output vector */                   
                                         out.push_back(x +                               'a'                               );                   
                             
                                         for                               (                               int                               i = 0; i < adj[x].size(); ++i) {                   
                                         if                               (vis[adj[x][i]])                   
                                         continue                               ;                   
                             
                                         /* Since we have already included the present                   
                                         character in the order, the number edges inward                   
                                         to this child node can be reduced*/                   
                                         in[adj[x][i]]--;                   
                             
                                         /* If the number of inward edges have been removed,                   
                                         we can include this node as a source node*/                   
                                         if                               (in[adj[x][i]] == 0)                   
                                         stk.push(adj[x][i]);                   
                                         }                   
                                         }                   
                             
                                         /* Check if all nodes(alphabets) have been visited.                   
                                         Order impossible if any one is unvisited*/                   
                                         for                               (                               int                               i = 0; i < MAX_CHAR; ++i)                   
                                         if                               (!vis[i]) {                   
                                         cout <<                               "Impossible"                               ;                   
                                         return                               ;                   
                                         }                   
                             
                                         for                               (                               int                               i = 0; i < out.size(); ++i)                   
                                         cout << out[i];                   
                     }                   
                             
                     // Driver code                   
                     int                               main()                   
                     {                   
                                         vector<string> v{                               "efgh"                               ,                               "abcd"                               };                   
                                         findOrder(v);                   
                                         return                               0;                   
                     }                   

输出：

zyxwvutsrqponmlkjihgfeadcb

这种方法的复杂性是显而易见的 O（N*| S |）+O（V+E） 哪里 |五| =26（节点数与字母数相同）和 |E| < N （因为每个单词最多创建一条边作为输入）。因此，总体复杂性是有限的 O（N*S+N） . |S| 表示每个单词的长度。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章