C ++外来字典
假设有一种新的外语，并且使用拉丁字母。但是，字母之间的顺序未知。我们有一个字典中的非空单词列表，这些单词按照这种新语言的规则按字典顺序排序。我们必须找到这种语言的字母顺序。
因此，如果输入类似于[“wrt”，“wrf”，“er”，“ett”，“rftt”]]，则输出将为“wertf”
为了解决这个问题，我们将遵循以下步骤-
定义一张称为学位的映射
定义一张称为图的映射
n：=字数
对于初始化i：=0，当i<字长时，更新（将i增加1），执行-
degree[words[i，j]]：=0
对于初始化j：=0，当j<word[i]的大小时，更新（将j增加1），执行-
对于初始化i：=0，当i<n-1，更新（将i增加1）时，执行-
x：=单词[i，j]
y：=单词[i+1，j]
如果x不等于y，则-
在图形[x]的末尾插入y
（将[y]的度数增加1）
从循环中出来
l：=单词[i]的最小大小和单词[i+1]的最小大小
对于初始化j：=0，当j<l时，更新（将j增加1），执行-
ret：=空字符串
定义一个队列q
对于每个键值对的度数，请执行-
将其插入q
如果其值等于0，则-
当（不是q为空）时，执行-
降低度[坐]1
如果degree[sit]等于0，则-
（增加坐位1）
插入q
x：=q的第一个元素
从q删除元素
ret：=ret+x
对于坐在图中的每个元素-
返回（如果ret的大小与度的大小相同，则返回ret，否则为空字符串）
例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string alienOrder(vector<string>& words) {
map<char, int> degree;
map<char, vector<char> > graph;
int n = words.size();
for (int i = 0; i < words.size(); i++) {
for (int j = 0; j < words[i].size(); j++) {
degree[words[i][j]] = 0;
}
}
for (int i = 0; i < n - 1; i++) {
int l = min((int)words[i].size(), (int)words[i + 1].size());
for (int j = 0; j < l; j++) {
char x = words[i][j];
char y = words[i + 1][j];
if (x != y) {
graph[x].push_back(y);
degree[y]++;
break;
}
}
}
string ret = "";
queue<char> q;
map<char, int>::iterator it = degree.begin();
while (it != degree.end()) {
if (it->second == 0) {
q.push(it->first);
}
it++;
}
while (!q.empty()) {
char x = q.front();
q.pop();
ret += x;
vector<char>::iterator sit = graph[x].begin();
while (sit != graph[x].end()) {
degree[*sit]--;
if (degree[*sit] == 0) {
q.push(*sit);
}
sit++;
}
}
return ret.size() == degree.size() ? ret : "";
}
};
main(){
Solution ob;
vector<string> v = {"wrt","wrf","er","ett","rftt"};
cout <<(ob.alienOrder(v));
}输入值
{"wrt","wrf","er","ett","rftt"}输出结果
wertf