Topological Sort
LC #269Hard
Alien Dictionary
Topological Sort
AmazonGoogleMetaBloombergAirbnbProblem
Given a sorted dictionary of an alien language, determine the order of characters.
graphtopological-sortbfsstring
Constraints
- ›1 ≤ words.length ≤ 100
- ›1 ≤ words[i].length ≤ 100
- ›Lowercase English letters only
- ›Return "" if invalid (cycle or word is prefix of earlier word)
Example
Input
words = ["wrt","wrf","er","ett","rftt"]Output
"wertf"Why
From adjacent pairs: t<f, w<e, r<t, e<r → order: w,e,r,t,f