105. Alien Dictionary
Infer an ordering of observed letters that is consistent with the supplied dictionary order. When several valid alphabets fit, return the lexicographically smallest one under this course's tie rule.
A longer word before its own complete prefix is inconsistent. Include letters that occur in words even when no pairwise ordering constraint mentions them.
Example 1
Input
[wrt,wrf,er,ett,rftt]
Output
Optional.of("wertf")Explanation: First differences imply t<f, w<e, r<t, and e<r. The chain includes every observed letter.
Example 2
Input
[za,zb,ca,cb]
Output
Optional.of("abzc")Explanation: a<b is observed twice but counted once; z<c is independent. A min-queue chooses a, then newly ready b before z.
Example 3
Input
[abc,ab]
Output
Optional.empty()
Explanation: Changing character ranks cannot make a longer word precede its own prefix.
Example 4
Input
["",""]
Output
Optional.of("")Explanation: There are no observed symbols and no contradictory word order.
Constraints
0 <= words.length <= 105sum(words[i].length) <= 105- Words contain lowercase English letters. Input order is the order in the unknown alphabet.
Hints
Hint 1
Compare neighboring words, stopping at the first different letter.
Hint 2
Check the longer-before-prefix contradiction and deduplicate inequalities.
Hint 3
Include isolated letters and repeatedly emit the smallest zero-indegree symbol.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Infer a constrained five-letter alphabet
["wrt","wrf","er","ett","rftt"]
"wertf"