Problem Statement
There is a dictionary containing words from an alien language for which we don't know the ordering of the letters.
Given a list of strings words from the alien language's dictionary. All strings in words are sorted lexicographically by the rules of this new language.
Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules.
It is given that the input is a valid dictionary and there exists an ordering among its letters.
Example 1:
Input: Words: ["ba", "bc", "ac", "cab"]
Output: bac
Explanation: Given that the words are sorted lexicographically by the rules of the alien language, so
from the given words we can conclude the following ordering among its characters:
1. From "ba" and "bc", we can conclude that 'a' comes before 'c'.
2. From "bc" and "ac", we can conclude that 'b' comes before 'a'
From the above two points, we can conclude that the correct character order is: "bac"
Example 2:
Input: Words: ["cab", "aaa", "aab"]
Output: cab
Explanation: From the given words we can conclude the following ordering among its characters:
1. From "cab" and "aaa", we can conclude that 'c' comes before 'a'.
2. From "aaa" and "aab", we can conclude that 'a' comes before 'b'
From the above two points, we can conclude that the correct character order is: "cab"
Example 3:
Input: Words: ["ywx", "wz", "xww", "xz", "zyy", "zwz"]
Output: ywxz
Explanation: From the given words we can conclude the following ordering among its characters:
1. From "ywx" and "wz", we can conclude that 'y' comes before 'w'.
2. From "wz" and "xww", we can conclude that 'w' comes before 'x'.
3. From "xww" and "xz", we can conclude that 'w' comes before 'z'
4. From "xz" and "zyy", we can conclude that 'x' comes before 'z'
5. From "zyy" and "zwz", we can conclude that 'y' comes before 'w'
From the above five points, we can conclude that the correct character order is: "ywxz"
Constraints:
1 <= words.length <= 1001 <= words[i].length <= 100words[i]consists of only lowercase English letters.
Why this is a Topological Sort problem
| What the question says | The signal it matches |
|---|---|
| "Return a string of the unique letters in the new alien language sorted" | the answer is a sequence |
| "All strings in words are sorted lexicographically by the rules of this new language" | the input describes dependencies between letters |
This is the derive the edges first variant: compare neighbouring words to learn the letter order.
The closest alternative. Sorting the letters with a custom comparison. It cannot work, because there is no rule to compare two letters with until the word list has been read. The order has to be discovered before anything can be sorted.
The introduction says the sort is not the hard part, and that is right. Take each pair of words that sit next to each other in the list. The first position where they differ gives one edge, from the earlier word's letter to the later word's letter. Positions after that first difference say nothing. Once every edge is collected, the rest is the standard queue walk from the first problem in this chapter.
Solution
Since the given words are sorted lexicographically by the rules of the alien language, we can always compare two adjacent words to determine the ordering of the characters. Take Example-1 above: [ba, bc, ac, cab]
-
Take the first two words
baandbc. Starting from the beginning of the words, find the first character that is different in both words: it would beafrombaandcfrombc. Because of the sorted order of words (i.e. the dictionary!), we can conclude thatacomes beforecin the alien language. -
Similarly, from
bcandac, we can conclude thatbcomes beforea. These two points tell us that we are actually asked to find the topological ordering of the characters, and that the ordering rules should be inferred from adjacent words from the alien dictionary.
This makes the current problem similar to Tasks Scheduling Order, the only difference being that we need to build the graph of the characters by comparing adjacent words first, and then perform the topological sort for the graph to determine the order of the characters.
Algorithm Walkthrough
Let's trace the first example, ["ba", "bc", "ac", "cab"]. Move through the steps one at a time:
Step 1. Two words that sit next to each other in a sorted list tell you about exactly one pair of letters: the first place where they differ. Everything before that is equal and says nothing, and everything after it is irrelevant, because the order was already decided at that first difference. 4 words give 3 neighbouring pairs here, and two of them happen to give the same rule, a before c, which is why c is waiting on 2.
1 of 5
Code
Here is what our algorithm will look like:
Time Complexity
In step d, each task can become a source only once and each edge (a rule) will be accessed and removed once. Therefore, the time complexity of the above algorithm will be O(V+E), where V is the total number of different characters and E is the total number of the rules in the alien language. Since, at most, each pair of words can give us one rule, therefore, we can conclude that the upper bound for the rules is O(N) where N is the number of words in the input. So, we can say that the time complexity of our algorithm is O(V+N).
Space Complexity
The space complexity will be O(V+N), since we are storing all of the rules for each character in an adjacency list.