Alien Dictionary

An alien language uses the lowercase English letters, but in an order you don't know. You are given an array of strings words from the dictionary of this language: the words are sorted in the alien alphabetical order.

Two words are compared letter by letter, as in any dictionary: at the first position where they differ, the word with the earlier letter comes first. If no position differs because one word is the beginning (a prefix) of the other, the shorter word comes first, so "ab" always comes before "abc".

Return a string with every letter that appears in words, each once, in the order of the alien alphabet. If the words contradict themselves, so that no order of the letters makes them sorted, return "" (an empty string). If several orders work, return the one that comes first in the usual alphabetical order: that makes the answer unique.

Example 1:

Input: words = ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"
Explanation: Each pair of neighbouring words tells us one thing, from the first letters where they differ:
    "wrt" before "wrf":  t comes before f
    "wrf" before "er":   w comes before e
    "er" before "ett":   r comes before t
    "ett" before "rftt": e comes before r
Chained together: w → e → r → t → f. These are all the letters of the words, and this is the only order that works.

Example 2:

Input: words = ["z", "x", "z"]
Output: ""
Explanation: "z" before "x" says z comes before x, but "x" before "z" says x comes before z.
The two facts form a cycle, so no order of the letters can make this list sorted.

Example 3:

Input: words = ["cb", "ca"]
Output: "bac"
Explanation: The words differ first at their second letters, so b comes before a. Nothing tells us where c goes.
The orders "bac", "bca" and "cba" all work; "bac" comes first alphabetically.

Constraints:

• 1 <= words.length <= 104
• 1 <= words[i].length <= 20
• words[i] consists of lowercase English letters. The same word can appear more than once.