查找字母顺序，以便可以将单词视为在C ++中排序
假设我们有一个单词数组，我们必须找到英语字母中的任何字母顺序，以便给定的单词可以被视为以升序排序（如果存在这样的顺序），否则返回“不可能”。
因此，如果输入像单词=[“efgh”，“wxyz”]，则输出将为zyxvutsrqponmlkjihgfewdcba
为了解决这个问题，我们将遵循以下步骤-
字母：=26
n：=v的大小
如果n与1相同，则-
显示“abcdefghijklmnopqrstuvwxyz”
返回
定义大小为ALPHABET的数组adj
定义大小为ALPHABET的数组，并填充0
pre：=v[0]
对于初始化i：=1，当i<n时，更新（将i增加1），-
显示“不可能”
返回
如果s[j]不等于pre[j]，则-
如果j<pre的大小和s的大小的最小值，则-
in[s[j]-'a'的ASCII]增加1
pre：=s
忽略以下部分，跳至下一个迭代
从循环中出来
在dj[pre[j]-'a'的ASCII]末尾插入s[j]-'a'的ASCII
s：=v[i]
对于范围从0到最小值（pre的大小和s的大小）的j-1−
如果pre的大小>s的大小，则-
pre：=s
定义一个堆栈my_stack
对于初始化i：=0，当i<ALPHABET时，更新（将i增加1），执行-
将我插入my_stack
如果in[i]等于0，则-
定义一个数组
定义大小为：的数组。26.用false填充
而（my_stack不为空），-
显示[i]
如果不是vis[i]不为零，则-
返回
显示“不可能”
如果vis[adj[x，i]]不为零，则-
（将[adj[x，i]]减少1）
如果in[adj[x，i]]与0相同，则-
忽略以下部分，跳至下一个迭代
将adj[x，i]插入my_stack
x：=my_stack的顶部元素
从my_stack中删除元素
vis[x]：=true
在out的末尾插入x+ASCII'a'
对于初始化i：=0，当i<adj[x]的大小时，更新（将i增加1），执行-
对于初始化i：=0，当i<ALPHABET时，更新（将i增加1），执行-
对于初始化i：=0，当i<outofsize，更新（将i增加1）时，执行-
例
让我们看下面的实现以更好地理解-
#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