【拓扑排序】火星辞书

LCR 114. 火星辞书

LCR 114. 火星辞书
​ 现有一种利用英语字母的外星文语言，这门语言的字母序次与英语序次差别。
​ 给定一个字符串列表 words ，作为这门语言的辞书，words 中的字符串已经 按这门新语言的字母序次举行了排序 。
​ 请你根据该辞书还原出此语言中已知的字母序次，并 按字母递增序次 分列。若不存在合法字母序次，返回 "" 。若存在多种大概的合法字母序次，返回此中 恣意一种 序次即可。
​ 字符串 s 字典序次小于 字符串 t 有两种环境：

• 在第一个差别字母处，如果 s 中的字母在这门外星语言的字母序次中位于 t 中字母之前，那么 s 的字典序次小于 t 。
  
• 如果前面 min(s.length, t.length) 字母都雷同，那么 s.length < t.length 时，s 的字典序次也小于 t 。
  

示例 1：

1. 输入：words = ["wrt","wrf","er","ett","rftt"]
2. 输出："wertf"

复制代码

示例 2：

1. 输入：words = ["z","x"]
2. 输出："zx"

复制代码

示例 3：

1. 输入：words = ["z","x","z"]
2. 输出：""
3. 解释：不存在合法字母顺序，因此返回 "" 。

复制代码

提示：

• 1 <= words.length <= 100
  
• 1 <= words.length <= 100
  
• words 仅由小写英笔墨母构成
  

留意：本题与主站 269 题雷同： https://leetcode-cn.com/problems/alien-dictionary/

---

解题思绪：拓扑排序

​ 这道题的题意实在不太好明白，很轻易让人以为 words 中每个字符串也是按照火星辞书的字母序次排序的，但是并没有，words 中每个字符串中出现的字母都是随机的，以是我们只必要关心字符串与字符串之间的关系即可！
​ 而且我们末了要得到的是每个字母之间的序次，实在就相称于是一个有向图的指向，以是我们可以根据字符串之间的巨细关系，推出每个字母之间的关系，让排序靠前的字母指向排序靠后的字母，末了来一个拓扑排序，得到的就是一个有指向关系的字符串效果！如下图所示：

​ 拓扑题目对我们来说是小题目，以是现在 题目变革为怎样创建这个图，让字母之间有序次的指向！
​ 现在的思绪就是，我们摆列 words 中的两两字符串举行比力，不外我们保持让 words 体现排在前面的字符串，让 words[j] 体现排在背面的字符串，如许子对比的话我们只必要写一份对比代码即可！
​ 然后比对过程中，我们将 words 和 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 的节点没被处置惩罚到，以是要提前将字符串中出现过的字母都初始化到入度表中，防止背面在拓扑排序的时间，连最开始的循环的进不去！
  

1. class Solution {
2. private:
3.     unordered_map<char, unordered_set<char>> edges; // 哈希表嵌套哈希表，是为了快速索引
4.     unordered_map<char, int> in_degree;             // 统计入度
5. public:
6.     string alienOrder(vector<string>& words) {
7.         // 1. 映射字母：将words中出现的字母初始化到in_degree中，否则后面会出现拿不到入度为0的节点的情况
8.         for(int i = 0; i < words.size(); ++i)
9.             for(int j = 0; j < words[i].size(); ++j)
10.                 in_degree[words[i][j]] = 0;
12.         // 2. 建图，以及入度的计算
13.         for(int i = 0; i < words.size() - 1; ++i)
14.         {
15.             for(int j = i + 1; j < words.size(); ++j)
16.             {
17.                 bool check = build(words[i], words[j]);
19.                 // 判断一下是否不符合规则：前面字符串的长度比后面字符串长度要长
20.                 if(check == true)
21.                     return "";
22.             }
23.         }
25.         // 3. 将所有入度为0的节点加入到队列中
26.         //  （在此之前必须将所有出现的字母都添加到in_degree中并且初始化为0，不然入度为0的节点没被算入）
27.         queue<char> bfs;
28.         for(auto& e : in_degree)
29.         {
30.             if(e.second == 0)
31.                 bfs.push(e.first);
32.         }
34.         // 4. 进行拓扑排序
35.         string ret;
36.         while(!bfs.empty())
37.         {
38.             char front = bfs.front();
39.             bfs.pop();
40.             ret += front; // 添加当前字母到结果集中
42.             // 将与front相连的节点的入度减一，如果出现入度为0的节点，则将其加入队列中
43.             for(auto& c : edges[front])
44.             {
45.                 in_degree[c]--;
46.                 if(in_degree[c] == 0)
47.                     bfs.push(c);
48.             }
49.             
50.             // 最后将当前节点从哈希表中删掉
51.             edges.erase(front);
52.         }
54.         // 5. 判断哈希表是否有没处理的节点，是的话说明存在环，则直接返回空即可
55.         return edges.size() == 0 ? ret : "";
56.     }
58.     bool build(const string& s1, const string& s2)
59.     {
60.         // 使用双指针方法，根据题目要求进行建图以及入度的计算
61.         int cur = 0;
62.         while(cur < s1.size() && cur < s2.size())
63.         {
64.             // 只有不相等才处理
65.             if(s1[cur] != s2[cur])
66.             {
67.                 char a = s1[cur], b = s2[cur]; // 这里是a->b
69.                 // 如果不存在由a->b的话，则将其加入图中
70.                 if(edges[a].count(b) == 0)
71.                 {
72.                     edges[a].insert(b);
73.                     in_degree[b]++;
74.                 }
76.                 // 因为只需要判断第一对不相等的字符，后面的字符是没有影响的，所以break
77.                 break;
78.             }
79.             cur++;
80.         }
82.         // 判断一下是否不符合规则：前面字符串的长度比后面字符串长度要长
83.         if(cur < s1.size() && cur == s2.size())
84.             return true;
85.         return false;
86.     }
87. };

复制代码