Asked at
Alien Dictionary
HardVerifiedTopological SortGraphDFS~35 min
You have a list of words sorted lexicographically by the rules of an unknown alien language. Derive a valid ordering of its letters.
Return any valid letter order as a string. If the ordering is invalid (a contradiction, or a longer word appearing before its own prefix), return an empty string.
The input arrives as a single string[].
Examples
in["wrt","wrf","er","ett","rftt"]
out"wertf"
Comparing adjacent words yields w<e, t<f, r<e, e<r, giving order wertf.
in["z","x","z"]
out""
z<x and x<z contradict each other, so no valid order exists.
Constraints
- 1 ≤ words.length ≤ 100
- 1 ≤ words[i].length ≤ 100
- words[i] consists of lowercase English letters.
- Words are sorted by the alien language's letter order.
Get help
🔑
Sign in to solve
Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.