Description
There is a new alien language that uses the English alphabet. The order of letters is unknown to you. You are given a list of strings words from the alien dictionary, sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
Examples
Input:
words = ["wrt","wrf","er","ett","rftt"]Output:
"wertf"Explanation:
From comparing adjacent words, the derived order is w->e->r->t->f.
Input:
words = ["z","x"]Output:
"zx"Explanation:
z comes before x in this alien language.
Input:
words = ["abc","ab","a"]Output:
""Explanation:
This input is invalid because 'abc' cannot come before 'ab' in any valid lexicographic ordering. A longer word with the same prefix must come after the shorter word, so an empty string is returned.
Constraints
- •
1 ≤ words.length ≤ 100 - •
1 ≤ words[i].length ≤ 100