返回题库

外星词典

Alien Dictionary

专题
Algorithmic Programming / 算法编程
难度
L4
来源
Citadel

题目详情

问题：外星词典

考察：图、字符串

来源：Citadel

链接：https://www.jointaro.com/interviews/questions/alien-dictionary/

There is a new alien language which uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language, and your task is to determine the order of the letters in this language.

Return a string of the letters in the correct order. If there is no valid ordering, return "". If there are multiple valid orderings, return any of them.

 

Example 1:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

Example 2:

Input: words = ["z","x"]
Output: "zx"

Example 3:

Input: words = ["z","x","z"]
Output: ""
Explanation: The order is invalid, so return "".

 

Constraints:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • words[i] consists of lowercase English letters.
解析

思路：把相邻单词的第一个不同字符转成有向边，表示字母先后关系；同时检查较长单词排在自身前缀之前的非法情况。之后对所有出现过的字母做拓扑排序，若无法取完所有节点则存在环，返回空串。

复杂度：设总字符数为 L，建图和拓扑排序都是 O(L)，空间 O(1) 到 O(26^2)。