Alien Dictionary
Hard · Graphs · Array · String · Depth-First Search · Breadth-First Search · Graph · Topological Sort
Problem
An alien language uses the lowercase English letters, but in an unknown order. You are given a list words that is claimed to be sorted lexicographically by the rules of that alien alphabet.
Return a string containing each distinct letter that appears in words exactly once, in an order consistent with the sorted list. If no letter order can make the list sorted, return "". If several orders work, return any of them; the tests accept every valid answer.
Lexicographic order works as usual: two words are compared at the first position where they differ. If one word is a prefix of the other, the shorter word comes first. So a longer word placed before its own prefix, such as "abc" before "ab", makes the list impossible.
Examples
Input: words = ["wrt","wrf","er","ett","rftt"] Output: "wertf"
Neighbors give t < f (wrt, wrf), w < e (wrf, er), r < t (er, ett) and e < r (ett, rftt). Together they force w, e, r, t, f.
Input: words = ["z","x"] Output: "zx"
z comes before x.
Input: words = ["z","x","z"] Output: ""
The list says z < x and then x < z, which no alphabet can satisfy.
Constraints
- 1 <= len(words) <= 100
- 1 <= len(words[i]) <= 100
- words[i] consists of lowercase English letters
Approaches
- Rules from every pair of words — time O(N² · L), space O(U²)
Follow-up
Many orders can be valid. How would you return the alphabetically smallest one, or decide whether the list pins down exactly one order? (Both are use cases of Course Schedule II.)
Related problems
Start free on Cariara · Coding problems · System design studio
