Alien Dictionary

Hard
Topological SortGraph

Alien Dictionary

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.

Example 1:

Input: ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

Example 2:

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

Examples

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: wertf
Input: words = ["z","x"]
Output: zx
Input: words = ["z","x","z"]
Output:

Constraints

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