Alien Dictionary
Alien Dictionary is a hard Advanced Graphs problem from the Blind 75. The key pattern is topological sort with a min-heap, and a good solution runs in O(total characters + alphabet log alphabet) time.
Problem
Infer the lexicographically smallest valid character order from sorted alien words, or print an empty string if impossible.
Examples
Example 1
Input
["baa","abcd","abca","cab","cad"]Output
"bdac"Example 2
Input
["qx","qz","xz","zq"]Output
"qxz"Example 3
Input
["abc","ab"]Output
""Approach
Compare each pair of adjacent words; their first differing letters give one ordering edge. A topological sort that always picks the smallest available letter gives the required order.
| Pattern | Topological sort with a min-heap |
|---|---|
| Time | O(total characters + alphabet log alphabet) |
| Space | O(alphabet²) |
Watch out for
A longer word listed before its own prefix, or any cycle, means no valid order: print an empty string.