Alien Dictionary
You are given a list of words sorted according to the rules of an unknown alphabet. Derive an ordering of the letters that is consistent with the list, or return an empty string if none exists. Any consistent ordering is acceptable.
- 1 ≤ words.length ≤ 100
- 1 ≤ word length ≤ 100
- Lowercase English letters
- Order constraints between letters come from the first differing character of adjacent words
- Constraints form a directed graph; an order exists iff it is acyclic
- Output a topological ordering
Constraints of the form "A before B" are edges in a directed graph; a valid schedule exists exactly when the graph has no cycle, and any topological order is a valid schedule. Kahn's algorithm (peel off zero in-degree nodes) also detects impossibility: if it stops before emitting every node, a cycle remains.
Compare each adjacent pair of words: the first position where they differ gives an edge a → b; if the second word is a proper prefix of the first, the input is invalid. Add every letter appearing in any word as a node. Run Kahn's algorithm over the letters; if the produced order contains all letters, return it, otherwise a cycle makes the dictionary inconsistent.
- DFS-based topological sort with cycle detection works equally well; the difficulty is in extracting constraints correctly, not in the sort.