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.
- 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.
words: A list of strings of size
n, representing the dictionary words sorted lexicographically in the alien language.
A string representing the smallest possible lexicographical order, or an empty string if no valid order exists.
1words = ["wrt","wrf","er","ett","rftt"]
1words = ["z","x"]
x，we can get
z < x.
2 <= n <= 10000
1 <= words[i] <= 30