题目

现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。

给定一个字符串列表 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] 仅由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/Jf1JuT
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

虽然是hard难度，但思路比较好想。

对于输入的单词数组，对于相邻的两个字符串两两比较，得到关于字母的先后顺序，形成一个图，规定较小的字母到较大的字母有一条「有向」的边。

建好图之后，使用拓扑排序，输出可能的字母先后顺序，并验证是否有环，如果有环返回空串，没有的话返回生成的字母顺序。

不过细节较多，见注释。

代码

  1. class Solution {
  2.     public String alienOrder(String[] words) {
  3.         int n = words.length;
  4.         int[] inDegree = new int[26];
  5.         // 初始化为-1，表示该字符不存在
  6.         Arrays.fill(inDegree, -1);
  7.         // 出现过的字符种类
  8.         int cnt = 0;
  9.         for (String word : words) {
  10.             for (char c : word.toCharArray()) {
  11.                 if (inDegree[c - 'a'] == -1) {
  12.                     cnt++;
  13.                 }
  14.                 inDegree[c - 'a'] = 0;
  15.             }
  16.         }
  17.         // key为一个字符，val为比其小的所有字符
  18.         // 这里使用set去重，不过好像用list也可以（如果发生了重复一定有环）
  19.         Map<Character, Set<Character>> graph = new HashMap<>();
  20.         // 比较相邻的两个单词，以生成字符先后顺序的图
  21.         for (int i = 1; i < n; i++) {
  22.             int p = 0;
  23.             int q = 0;
  24.             int len1 = words[i - 1].length();
  25.             int len2 = words[i].length();
  26.             // 找第一个不相同的字母
  27.             while (p < len1 && q < len2 && words[i - 1].charAt(p) == words[i].charAt(q)) {
  28.                 p++;
  29.                 q++;
  30.             }
  31.             // 后面的字符串遍历完了，前面的字符串还剩余字母，例如abcd和abc，其实这种用例不符合条件不应该出现
  32.             if (p < len1 && q == len2) {
  33.                 return "";
  34.             } else if (p < len1 && q < len2) {
  35.                 // 都剩余字母没遍历完，当前p和q指向的字符就是不同的，例如abd和abc，那么就建立一条d到c的边，表示d比c小
  36.                 char c1 = words[i - 1].charAt(p);
  37.                 char c2 = words[i].charAt(q);
  38.                 boolean res = graph.computeIfAbsent(c1, k -> new HashSet<>()).add(c2);
  39.                 // 只有c1的set中第一次添加c2，才增加c2的入度
  40.                 if (res) {
  41.                     inDegree[c2 - 'a']++;
  42.                 }
  43.             }
  44.         }
  45.         // 剩下就是拓扑排序基本写法，这里是BFS
  46.         Queue<Character> q = new LinkedList<>();
  47.         for (int i = 0; i < 26; i++) {
  48.             if (inDegree[i] == 0) {
  49.                 q.offer((char) (i + 'a'));
  50.             }
  51.         }
  52.         StringBuilder sb = new StringBuilder();
  53.         while (!q.isEmpty()) {
  54.             char cur = q.poll();
  55.             sb.append(cur);
  56.             Set<Character> l = graph.get(cur);
  57.             // 注意cur可能不存在比其大的字母
  58.             if (l == null) {
  59.                 continue;
  60.             }
  61.             for (char c : l) {
  62.                 inDegree[c - 'a']--;
  63.                 if (inDegree[c - 'a'] == 0) {
  64.                     q.offer(c);
  65.                 }
  66.             }
  67.         }
  68.         // 如果sb长度小于字符种类，一定是有环
  69.         return sb.length() == cnt ? sb.toString() : "";
  70.     }
  71. }