困难

问题描述

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

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

注意：本题与主站 269 题相同：https://leetcode-cn.com/problems/alien-dictionary/ (opens new window)

拓扑排序

这是一道拓扑排序的题目。根据字符串列表构建图，因为字符串列表 $\text {words}$ 中的单词已经 按这门新语言的字母顺序进行了排序， 从左到右遍历外星文字典中的两个相邻单词中的字母，当遇到首个不相同的字母时，前一个单词的字母 $\text {c1}$ 的字典序 比 后一个单词的字母 $\text {c2}$ 的字典序要小，增加 $\text {c2}$ 的入度，$\text {c1}$ 增加邻接字母 $\text {c2}$。如果相邻两个单词，后面的单词是前面的单词的前缀，且后面的单词的长度小于前面的单词的长度，如 $words=["ab","a"]$ ，这样的字符串列表是不合法的，直接返回 "" 即可。

当且仅当有向图中无环时，才有拓扑排序，且拓扑排序可能不止一种。如果有向图中有环，某些字母的入度不能减到 $0$ ,说明字母不存在符合要求的排列。

拓扑排序的流程是，在建图完成后，我们将所有入度为 $0$ 的字母（没有比这些字符字典序更小的字母）入队，将这些字母的邻接字母的入度减 $1$，删除该字母，若有新的入度为 $0$ 的点，则将其进行入队操作，重复操作，直到队列清空。若最终得到的排序结果的字母个数跟单词列表中的字母个数相同，则说明无环，数组拓扑排序结果，否则说明有环，不存在符合要求的排列。

/**
 * @param {string[]} words
 * @return {string}
 */
var alienOrder = function (words) {
  const graph = new Map()
  const indegree = new Map()
  const queue = []
  const ans = []
  words.forEach((word) => {
    for (let i = 0; i < word.length; i++) {
      const char = word[i]
      if (!graph.has(char)) {
        graph.set(char, [])
        indegree.set(char, 0)
      }
    }
  })
  for (let i = 0; i < words.length - 1; i++) {
    const w1 = words[i]
    const w2 = words[i + 1]
    const len1 = w1.length
    const len2 = w2.length
    const len = Math.min(len1, len2)
    let valid = false
    for (let j = 0; j < len; j++) {
      if (w1[j] !== w2[j]) {
        valid = true
        graph.get(w1[j]).push(w2[j])
        indegree.set(w2[j], indegree.get(w2[j]) + 1)
        break
      }
    }
    if (!valid && len1 > len2) return ''
  }
  for (const char of indegree.keys()) {
    if (indegree.get(char) === 0) {
      queue.push(char)
      indegree.delete(char)
    }
  }
  while (queue.length) {
    const char = queue.shift()
    ans.push(char)
    const arr = graph.get(char)
    for (const x of arr) {
      const count = indegree.get(x) - 1
      indegree.set(x, count)
      if (count === 0) {
        queue.push(x)
        indegree.delete(x)
      }
    }
  }
  return ans.length === graph.size ? ans.join('') : ''
}

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$