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