Alien Dictionary
Question (LC.269)
The new alien language uses [a-z]. But the order of the letter is unknown.
Given a list of nonempty words from the alien dictionary (where words are sorted), derive the order of letters in this alien language.
Example
Input: ["z", "x"]
Output: "zx"
There may be multiple valid order of letters, return any one of them is fine.]
Input: ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"
If the order is invalid, return an empty string.
Input: ["z", "x", "z"]
Output: ""
You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
Input: ["z", "an"]
Output: "zan" (n cannot be a prefix of z by this rule)
Analysis
We can think of this as a way to linearize the dependencies.
Two challenges:
- How to infer the dependency? (draw edges)
- How to store the graph structure?
Reference
Alien Dictionary by Ethan Li