240. Alien Dictionary — Topological Sort

Hard · Graph

Given a sorted list of words from an alien language, derive the lexicographic order of the alien alphabet. Return any valid ordering, or "" if it is impossible (contradictory constraints).

Examples

Example 1
Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
Explanation: Derived order: w→e→r→t→f

Example 2
Input: words = ["z","x","z"]
Output: ""
Explanation: z→x and x→z form a cycle

Constraints

• 1 ≤ words.length ≤ 100, 1 ≤ words[i].length ≤ 100