数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学C++ 外星词典
假设存在一种新的外星语言，它使用拉丁字母表。但是，字母之间的顺序是未知的。我们有一份来自词典的非空单词列表，这些单词按照这种新语言的规则按字典顺序排序。我们必须找到这种语言中字母的顺序。
因此，如果输入类似于 ["wrt","wrf","er", "ett", "rftt" ]，则输出将为 "wertf"
为了解决这个问题，我们将遵循以下步骤：
定义一个名为 degree 的映射
定义一个名为 graph 的映射
n := 单词的数量
对于初始化 i := 0，当 i < 单词的数量 时，更新（i 增加 1），执行：
对于初始化 j := 0，当 j < words[i] 的大小 时，更新（j 增加 1），执行：
degree[words[i, j]] := 0
对于初始化 i := 0，当 i < n - 1 时，更新（i 增加 1），执行：
l := words[i] 的大小和 words[i + 1] 的大小的最小值
对于初始化 j := 0，当 j < l 时，更新（j 增加 1），执行：
x := words[i, j]
y := words[i + 1, j]
如果 x 不等于 y，则：
将 y 插入到 graph[x] 的末尾
（degree[y] 增加 1）
退出循环
ret := 空字符串
定义一个队列 q
对于 degree 中的每个键值对 it，执行：
如果 it 的值为 0，则：
将 it 的键插入到 q 中
当 (q 不为空) 时，执行：
x := q 的第一个元素
从 q 中删除元素
ret := ret + x
对于 graph 中的每个元素 sit，执行：
degree[sit] 减 1
如果 degree[sit] 等于 0，则：
将 sit 插入到 q 中
（sit 增加 1）
返回（如果 ret 的大小等于 degree 的大小，则返回 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
455 次浏览
