【LintCode】892.外星人字典

本文主要是介绍【LintCode】892.外星人字典，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

描述

有一种新的使用拉丁字母的外来语言。但是，你不知道字母之间的顺序。你会从词典中收到一个 非空的 单词列表，其中的单词在这种新语言的规则下按字典顺序排序。请推导出这种语言的字母顺序。

注意：

1. 你可以假设所有的字母都是小写。
2. 如果字符串 a 是字符串 b 的前缀，且 b 出现在 a 之前，那么这个顺序是无效的。
3. 如果顺序是无效的，则返回空字符串。
4. 这里可能有多个有效的字母顺序，返回以正常字典顺序看来最小的。
5. 一个字符串中的字母默认是同一等级的，且按照人类字典序排序。

样例

样例1

输入：["wrt","wrf","er","ett","rftt"]
输出："wertf"
解释：
从 "wrt"和"wrf" ,我们可以得到 't'<'f'
从 "wrt"和"er" ,我们可以得到'w'<'e'
从 "er"和"ett" ,我们可以得到 get 'r'<'t'
从 "ett"和"rftt" ,我们可以得到 'e'<'r'
所以返回 "wertf"

样例2：

输入：["z","x"]
输出："zx"
解释：
从 "z" 和 "x"，我们可以得到 'z' < 'x'
所以返回"zx"

原题链接

892.外星人字典

思路

先比较相邻的字符串，能生成一条边，如"bck" “bak”，根据顺序可生成一条 c 指向 a 的边，即c->a。

根据这些生成的边得到一个图，再对该图进行拓扑排序。

更详细的分析见 Leetcode 269.火星词典

代码

class Solution {
public:/*** @param words: a list of words* @return: a string which is correct order*/string alienOrder(vector<string> &words) {if (words.size() == 0) return "";unordered_map<char, int> indegree; //入度表//如果a->b，则b的入度为1for (int i = 0; i < words.size(); i++) {for (char c : words[i]) {indegree[c] = 0; //初始时，所有字符的入度都为0}}//比如a->b，a->c，则key为a，value为{b, c}//记录字符的后继字符（邻居）unordered_map<char, unordered_set<char>> graph;for (int i = 0; i < words.size() - 1; i++) {//比较相邻字符串(当前字符串和下一个字符串），找边string cur = words[i];string next = words[i + 1];//需要比较的长度是两个字符串中较小的长度，重叠的部分才有可能产生边//如bck和bckf只需要比较3个字符长度即可,int len = min(cur.size(), next.size()); int j = 0;for (; j < len; j++) {if (cur[j] != next[j]) { //找到一条边如absfk和abcf，找到一条边s->cif (!graph[cur[j]].count(next[j])) { //同一条边不要重复加入度graph[cur[j]].insert(next[j]);indegree[next[j]]++; }break; //找到一条边就跳出当前循环}}if (j < cur.size() && j == next.size()) { //cur的长度 > next的长度，如bckf 和 bck，这种情况就无字典序return "";}}//拓扑排序string ans;priority_queue<char, vector<char>, greater<char>> que;for (auto it : indegree) {if (it.second == 0) { //所有入度为0的点先入队que.push(it.first);} }while (!que.empty()) {char cur = que.top();que.pop();ans += cur;if (graph.count(cur)) { for (char next : graph[cur]) { if (--indegree[next] == 0) { //cur的邻居的入度全部减1，再将邻居入度为0的入队que.push(next); }}}}//如"zy""zx"，应该输出"yxz"//"ad","abc"应该输出"abcd"return ans.size() == indegree.size() ? ans : "";}
};

这篇关于【LintCode】892.外星人字典的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---