为什么要做手机网站开发,做机械方面外贸最大的网站,进入网站wordpress配置,链接网站制作题目描述#xff1a; 现有一种使用英语字母的火星语言#xff0c;这门语言的字母顺序与英语顺序不同。
给你一个字符串列表 words #xff0c;作为这门语言的词典#xff0c;words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
请你根据该词典还原出此语言中已知…题目描述 现有一种使用英语字母的火星语言这门语言的字母顺序与英语顺序不同。
给你一个字符串列表 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(vectorstring words) {mapchar, unordered_setchar m;int n words.size(), count 0;vectorint 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将每个字符的度数设置为其实际度数。queuechar 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) 次操作。
