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:
Given the following words in dictionary,
[ "wrt", "wrf", "er", "ett", "rftt" ]
The correct order is: "wertf"
.
Example 2:
Given the following words in dictionary,
[ "z", "x" ]
The correct order is: "zx"
.
Example 3:
Given the following words in dictionary,
[ "z", "x", "z" ]
The order is invalid, so return ""
.
Note: