Aliens use the English letters, but in a different order that you do not know.
You get a list words taken from an alien dictionary. The words in the list are already sorted by the alien rules. Compare two neighbouring words letter by letter. The first place where they differ tells you which letter comes earlier in the alien order.
Return a string with all the letters that appear in words, arranged in the alien order. If the list cannot be right (the rules fight each other), return "".
Which answer to return: several orders can obey the rules, but the judge has only one answer stored. Build the order letter by letter. If two or more letters are free to go next, choose the one that is earliest in the ordinary English alphabet (a before b). Letters that no rule talks about must still appear in the answer.
Examples
Example 1:
Input: words = ["ca","cb","ab"]
Output: "cab"
Explanation: "ca" before "cb" gives a before b. "cb" before "ab" gives c before a. So the order is c, a, b.
Example 2:
Input: words = ["bd","bc"]
Output: "bdc"
Explanation: The only rule is d before c. Letter b is free, and "b" comes first in the alphabet, so b is placed first.
Example 3:
Input: words = ["pqr","pq"]
Output: ""
Explanation: A longer word cannot come before its own beginning, so the list is not valid.