本文主要是介绍Leetcode 268 火星词典，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：
现有一种使用英语字母的火星语言，这门语言的字母顺序与英语顺序不同。
给你一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回 "" 。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。
字符串 s 字典顺序小于 字符串 t 有两种情况：
在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。
示例：
示例 1：
输入：words = ["wrt","wrf","er","ett","rftt"]
输出："wertf"
示例 2：
输入：words = ["z","x"]
输出："zx"
示例 3：
输入：words = ["z","x","z"]
输出：""
解释：不存在合法字母顺序，因此返回 "" 。
提示：
1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 仅由小写英文字母组成
class Solution
{
public:string alienOrder(vector<string>& words) {map<char, unordered_set<char>> m;int n = words.size(), count = 0;vector<int> degree(26, -1);string result = "";for (int i = 0; i < n - 1; i++)
//遍历给定的单词列表，比较相邻单词的对应字符，如果字符不同，则在映射m中插入该字符及其后续字符{for (int j = 0; j < min(words[i].size(), words[i + 1].size()); j++) {if (words[i][j] != words[i + 1][j]) {m[words[i][j]].insert(words[i + 1][j]);break;} else if (j == min(words[i].size(), words[i + 1].size()) - 1 and words[i].size() > words[i + 1].size()) return result;
//如果相邻单词的长度不同，且较长的单词先出现，则直接返回空字符串。}}for (const auto& word : words) for (const auto& c : word) degree[c - 'a'] = 0;//遍历给定的单词列表，将每个字符的度数设置为0。for (const auto& [key, value] : m) for (const auto& v : m[key]) ++degree[v - 'a'];
//根据映射m，将每个字符的度数设置为其实际度数。queue<char> q; //创建一个队列q，用于存储度数为0的字符。
//遍历26个字符，将度数为0的字符添加到队列q中。for (int i = 0; i < 26; i++) {if (!degree[i]) q.push((char)(i + 'a'));if (degree[i] != -1) ++count;}
//创建一个空字符串result，用于存储最终的排序顺序。
//当队列q不为空时，执行以下操作： a. 从队列q中取出一个字符u。 b. 将字符u添加到结果字符串result中。 c. 如果映射m中包含字符u，则遍历其后续字符v，将度数减1，如果度数变为0，则将字符v添加到队列q中。while (!q.empty()) {auto u = q.front();q.pop();result += u;if (m.count(u)) {for (const auto& v : m[u]) {--degree[v - 'a'];if (!degree[v - 'a']) q.push(v);}}}
//如果结果字符串result的长度等于count，则返回result，否则返回空字符串。return result.size() == count ? result : "";}
};
分析——————————————————————————————————
1.初始化一个映射 m 来记录每个字符可以转换成哪个字符，初始化为空集合。
2.初始化一个数组 degree 来记录每个字符的入度（即有多少字符可以转换到它），初始化为 -1。
3.初始化一个空字符串 result 来记录最终的顺序。
4.遍历 words 列表，比较每对相邻字符串。
1）如果相邻字符串在相同位置上的字符不同，那么记录它们之间的转换关系，即将 words[i][j] 转换为 words[i + 1][j]，并将其添加到 m[words[i][j]] 集合中。
2）如果相邻字符串在相同位置上的字符相同，且已经比较到字符串末尾，并且第一个字符串比第二个字符串长，那么直接返回空字符串，因为没有有效的顺序可以满足这些条件。
5.再次遍历 words 列表，初始化 degree 数组，记录每个字符的入度。
6.再次遍历 m 映射，更新 degree 数组，记录每个字符的入度。
7.初始化一个队列 q，并将所有入度为 0 的字符加入队列。
8.当队列不为空时，执行以下操作：
9.从队列中取出一个字符（入度为 0 的字符）。
10.将该字符添加到 result 字符串中。
1）如果该字符在 m 映射中有孩子节点，那么遍历这些孩子节点：减少它们对应的 degree 值。
2）如果减少后 degree 值为 0，那么将它们加入队列。
11.最后，如果 result 字符串的长度等于字符总数（即 count），则返回 result；否则返回空字符串，表示没有有效的顺序。
这个算法的时间复杂度是 O(NK^2)，其中 N 是单词列表的长度，K 是单词的平均长度。这是因为我们需要遍历每个单词的所有字符，并且对于每个字符，我们可能需要遍历它的所有孩子节点。在最坏的情况下，这可能会有 O(NK^2) 次操作。
这篇关于Leetcode 268 火星词典的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
