Array
String
Depth-First Search
Breadth-First Search
Graph
Topological Sort
There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.
You are given a list of strings `words` from the alien language's dictionary, where the strings in `words` are **sorted lexicographically** by the rules of this new language.
Derive the order of letters in this language, and return *it as a string* `order`. If there is no solution, return `""`. If there are multiple solutions, return *any one of them*.
For grading purposes on this platform, the chosen test cases each have a unique valid ordering.
Example 1
Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
Example 2
Input: words = ["z","x"]
Output: "zx"
Example 3
Input: words = ["z","x","z"]
Output: ""
Constraints
- •
1 <= words.length <= 100 - •
1 <= words[i].length <= 100 - •
words[i] consists of only lowercase English letters. - •
If multiple solutions exist, you only need to return any one of them.