Alien Dictionary

Hard

There is a new alien language that uses the English alphabet. However, the order among letters is unknown. You are given a list of strings words from the alien language dictionary, where the strings are sorted lexicographically by the rules of this new language.

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If no valid order exists, return "". If there are multiple valid orderings, return any of them.

Example 1

Input:  words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
Explanation: From "wrt" and "wrf": t < f. From "wrt" and "er": w < e. From "er" and "ett": r < t. From "ett" and "rftt": e < r.

Example 2

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

Example 3

Input:  words = ["z","x","z"]
Output: ""
Explanation: Invalid ordering — cycle detected.

Constraints

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