【拓扑排序】火星词典
文章目录
- LCR 114. 火星词典
- 解题思路：拓扑排序
LCR 114. 火星词典
LCR 114. 火星词典
现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。
给定一个字符串列表 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 <= 1001 <= words[i].length <= 100words[i]仅由小写英文字母组成
注意：本题与主站 269 题相同： https://leetcode-cn.com/problems/alien-dictionary/
解题思路：拓扑排序
这道题的题意其实不太好理解，很容易让人以为 words 中每个字符串也是按照火星词典的字母顺序排序的，但是并没有，words 中每个字符串中出现的字母都是随机的，所以我们只需要关心字符串与字符串之间的关系即可！
并且我们最后要得到的是每个字母之间的顺序，其实就相当于是一个有向图的指向，所以我们可以根据字符串之间的大小关系，推出每个字母之间的关系，让排序靠前的字母指向排序靠后的字母，最后来一个拓扑排序，得到的就是一个有指向关系的字符串结果！如下图所示：
拓扑问题对我们来说是小问题，所以现在 问题转变为如何建立这个图，让字母之间有次序的指向！
现在的思路就是，我们枚举 words 中的两两字符串进行比较，不过我们保持让 words[i] 表示排在前面的字符串，让 words[j] 表示排在后面的字符串，这样子对比的话我们只需要写一份对比代码即可！
然后比对过程中，我们将 words[i] 和 words[j] 交给 build() 函数去根据题目要求进行建图以及入度的计算即可，这里使用的是双指针的思想，但是我们只需要用一个变量 cur 来表示字符串当前的位置即可，因为我们要比对的是字符串中每个对应位置的字母！
比对的步骤如下所示：
- 用一个变量
cur表示s1和s2的对应字符，然后开始遍历两个字符串。 - 遍历过程中，只有遇到
s1[cur]和s2[cur]不相等才进行处理：- 如果相等的话，此时的对比没有意义，因为我们要找到其大小关系。
- 如果不相等的话，此时因为
s1是排在s2前面的，所以就能得到s1[cur]一定是排在s2[cur]前面的，也就是说s1[cur]指向s2[cur]，所以我们将这个指向添加到邻接表中，然后 让s2[cur]的入度加一即可！ - 因为只需要判断第一次出现不相等的字母，而后面的字母就没有影响了，所以 直接
break。
- 循环上述操作直到
cur走完s1或者s2字符串为止。 - 最后需要判断一下是否不符合规则：也就是判断前面字符串的长度是否比后面字符串长度要长，长的话是不行的，因为
"abc"和"ab"对比的话根据题目的要求是"abc"排在后面的，此时就错了，所以 如果前面字符串的长度比后面字符串长度要长，则该函数返回false。
剩下就是处理一些细节问题了：
- 因为这道题邻接表存放的是字符，所以我们得用哈希表
unordered_map<char, vector<char>>来作为邻接表的结构，但是因为考虑到在对比过程中我们需要做去重，而去重的内容就是哈希表中的vector<char>部分，此时如果每次都要遍历数组去判断是否存在重复内容的话，就太慢了，所以考虑将数组改为哈希表来存储，最后得到的结构就是unordered_map<char, unordered_set<char>>来作为邻接表，还能达到快速索引判重的效果！ - 因为我们在对比字符串的时候，对于不相等字母处理的时候，如果不存在该指向的话，是需要将其加入到建图内容中的，此时还要让被指向的节点的入度减一，因为存放的是字母，所以我们就用 哈希表来存储每个节点的入度，所以最后的结构就是
unordered_map<char, int>。 - 我们 需要在最开始就初始化入度表，因为后面在建图的时候可能那些入度为
0的节点没被处理到，所以要提前将字符串中出现过的字母都初始化到入度表中，防止后面在拓扑排序的时候，连最开始的循环的进不去！
class Solution {
private:
unordered_map<char, unordered_set<char>> edges; // 哈希表嵌套哈希表，是为了快速索引
unordered_map<char, int> in_degree; // 统计入度
public:
string alienOrder(vector<string>& words) {
// 1. 映射字母：将words中出现的字母初始化到in_degree中，否则后面会出现拿不到入度为0的节点的情况
for(int i = 0; i < words.size(); ++i)
for(int j = 0; j < words[i].size(); ++j)
in_degree[words[i][j]] = 0;
// 2. 建图，以及入度的计算
for(int i = 0; i < words.size() - 1; ++i)
{
for(int j = i + 1; j < words.size(); ++j)
{
bool check = build(words[i], words[j]);
// 判断一下是否不符合规则：前面字符串的长度比后面字符串长度要长
if(check == true)
return "";
}
}
// 3. 将所有入度为0的节点加入到队列中
// （在此之前必须将所有出现的字母都添加到in_degree中并且初始化为0，不然入度为0的节点没被算入）
queue<char> bfs;
for(auto& e : in_degree)
{
if(e.second == 0)
bfs.push(e.first);
}
// 4. 进行拓扑排序
string ret;
while(!bfs.empty())
{
char front = bfs.front();
bfs.pop();
ret += front; // 添加当前字母到结果集中
// 将与front相连的节点的入度减一，如果出现入度为0的节点，则将其加入队列中
for(auto& c : edges[front])
{
in_degree[c]--;
if(in_degree[c] == 0)
bfs.push(c);
}
// 最后将当前节点从哈希表中删掉
edges.erase(front);
}
// 5. 判断哈希表是否有没处理的节点，是的话说明存在环，则直接返回空即可
return edges.size() == 0 ? ret : "";
}
bool build(const string& s1, const string& s2)
{
// 使用双指针方法，根据题目要求进行建图以及入度的计算
int cur = 0;
while(cur < s1.size() && cur < s2.size())
{
// 只有不相等才处理
if(s1[cur] != s2[cur])
{
char a = s1[cur], b = s2[cur]; // 这里是a->b
// 如果不存在由a->b的话，则将其加入图中
if(edges[a].count(b) == 0)
{
edges[a].insert(b);
in_degree[b]++;
}
// 因为只需要判断第一对不相等的字符，后面的字符是没有影响的，所以break
break;
}
cur++;
}
// 判断一下是否不符合规则：前面字符串的长度比后面字符串长度要长
if(cur < s1.size() && cur == s2.size())
return true;
return false;
}
};