Alien Dictionary
Prereq: Topological Sort, Heap
Note that this problem requires knowing heap, which is covered in the Priority Queue/Heap section. If you are working through the content in order, feel free to skip this problem and come back after you have completed the heap section.
There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you.
You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language.
Derive the order of letters in this language.
Note:
- You may assume all letters are in lowercase.
- Every letter that appears in the input must also appear in the output, and your output cannot have characters not in the input.
- If no ordering of letters makes the dictionary sorted lexicographically, return an empty string.
- There may be multiple valid orders. If that's the case, return the smallest in normal lexicographical order.
Input & Output
Input
words — A list of strings of size `n`, representing the dictionary words sorted lexicographically in the alien language.
Output
A string representing the smallest possible lexicographical order, or an empty string if no valid order exists.
Example
Input
words = ["wrt","wrf","er","ett","rftt"]
Output
wertf
Explanation
Example
Input
words = ["z","x"]
Output
zx
Explanation
From z and x，we can get z < x.
So return zx.
Constraints
2 <= n <= 100001 <= words[i].length <= 30