Alien Dictionary
Hard
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.
Time Complexity
O(C)
Space Complexity
O(1)
14
Case 1
Input: ["wrt","wrf","er","ett","rftt"]
Expected: wertf
Case 2
Input: ["z","x"]
Expected: zx
Case 3
Input: ["z","x","z"]
Expected: