Alien Dictionary
Hard
An alien language uses lowercase English letters, but in an unknown order. You're given a list of words from its dictionary, sorted in that language's alphabetical order.
Return a string of the unique letters in words, arranged in an order consistent with how the words are sorted. If no order of letters could produce this sorting, return "". If several orders work, you can return any of them.
Words are compared the usual way: by the first position where they differ, and a word comes before any longer word that starts with it.
Example 1
Input: words = ["bca", "aaa", "acb"] Output: "bac"
bca comes before aaa, so b comes before a. aaa comes before acb, so a comes before c.
Example 2
Input: words = ["abc", "ab"] Output: ""
ab is a prefix of abc, so it has to come first under any order of letters.
Constraints
1 <= words.length <= 1001 <= words[i].length <= 100words[i]contains only lowercase English letters.
Approach
Adjacent words in the sorted list hold all the information there is. At the first position where two adjacent words differ, the letter in the first word comes before the letter in the second. Later positions tell you nothing, because the order was already decided. Each of these facts is a directed edge from one letter to another, and a valid alphabet is any topological order of that graph.
Kahn's algorithm builds the order by repeatedly taking a letter with no unplaced letters that must come before it. If some letters are never placed, they're part of a cycle, and no alphabet works. One more case produces no edges at all: a longer word that comes right before its own prefix, such as abc before ab. Check for it while comparing words.
Steps
- Collect every letter that appears, with an empty set of outgoing edges and an in-degree of
0. - For each pair of adjacent words, find the first position where they differ and add an edge from the first word's letter to the second word's letter, skipping edges you already have. If there's no difference and the first word is longer, return
"". - Put every letter with in-degree
0in a queue. Repeatedly remove a letter, add it to the order, and lower the in-degree of the letters after it, queueing any that reach0. - If the order contains every letter, return it. Otherwise, return
"".
Complexity
- Time:
O(C), whereCis the total number of characters across all words. The graph has at most 26 letters and 26² edges, so the sort itself takes constant time. - Space:
O(1)for the graph, since the alphabet has at most 26 letters.
Common mistakes
- Taking ordering facts from every differing position, or from non-adjacent words. Only the first difference between adjacent words is reliable.
- Missing the prefix case.
["abc", "ab"]produces no edges, so a plain topological sort would return an answer even though no alphabet works. - Adding the same edge twice and counting it twice in the in-degree. Store each letter's outgoing edges in a set.
Interview experiences
1 sharedRelated questions
Flatten a DictionaryRelated courses
