Alien Dictionary
Hard · Advanced Graphs
You are given a list of words from an alien language, written using some subset of lowercase English letters. The words are already sorted according to that alien language's alphabet order. Figure out one valid ordering of the letters that is consistent with the given words, and return it as a single string containing each distinct letter exactly once. If the given list can't correspond to any valid letter ordering (the rules contradict each other, or a word implies a letter comes before a strict prefix of itself), return an empty string. If more than one ordering would be valid, returning any one of them is acceptable.
Examples
Input: words = ["wrt","wrf","er","ett","rftt"]
Output: wertf
Why: Comparing adjacent words letter by letter gives the constraints w<e, r<t, e<r, t<f, which chain together into the order w,e,r,t,f.Input: words = ["z","x"]
Output: zx
Why: The only constraint is z before x, so that ordering works.Input: words = ["abc","ab"]
Output:
Why: abc comes after its own prefix ab in the list, which can never happen in a correctly sorted dictionary, so no order exists.Constraints
1 <= words.length <= 100, 1 <= words[i].length <= 20, words[i] consists of lowercase English letters only
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Alien Dictionary. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.