Given a sorted dictionary of an alien language, find the order of characters in the alphabet.
Input: ["baa", "abcd", "abca", "cab", "cad"]
Input: words = ["caa", "aaa", "aab"]
Input parameters: Function has one argument, an array of strings, and the dictionary sorted in the lexicographical order of the alien language.
Output: Return a string consisting of all the characters of the alien alphabet in order.
One simple but suboptimal solution is:
Now, let's think about an optimal solution.
If you're familiar with topological sort and what it means, you'll see that the solution to this problem is a simple application of topological sort.
Here’s a quick recap: Topological sort is ordering the vertices in a directed graph such that vertex A appears before vertex B for all directed edges A->B. One way to look at it is that you're given a graph of dependencies, and you have to order the vertices such that no dependencies are broken.
So, what is the graph in this question?
A lexicographically sorted dictionary gives us some information about the order of characters in the alphabet. In other words, from the dictionary, we can figure out that certain characters precede certain other characters in the alphabet.
How do we determine these relationships between characters in practice?
We know a few things about the order of the dictionary. In a dictionary, between two adjacent words, one of the following is true:
(We assume that words do not repeat in the dictionary. In an interview, it's worth establishing such assumptions explicitly, especially if your algorithm depends on it. Our algorithm won't really care, though.)
If (1) is true, we know from the dictionary property that the character at the mismatch index in the left word appears before its counterpart in the right word in the alphabet.
("mismatch index" is the lowest index for which word1[index] != word2[index] is true; for example, for "abcx" and "abcyz," the mismatch index is 3 (zero-based) and the different characters are "x" and "y")
Note: If (1) is false but (2) is true, we get no meaningful information because the shorter word will always appear earlier in the dictionary regardless of what characters the longer word ends with. Also, between two adjacent words, the characters after the first mismatch do not convey any relationship between the characters.
So, to solve our problem, we can start by comparing two adjacent words and try to find a mismatch. The first mismatch denotes that the letter in the first word will come before the respective letter in the second word in the alien language.
Let's look at an example to understand this:
Then we compare:
So, here’s the information we’ve got from this comparison:
Combining them, we can figure out that the order of characters is “cab” in the given alien language.
Next, we can use a directed graph to combine the information collected by comparing words. Add a directed edge between the first mismatched characters. Our directed graph will be a directed acyclic graph. Now, we can use topological sort on the DAG to get the order of characters.
O(total number of characters).
In the solution, one word will be compared not more than twice — once with the previous word and second with the next word. So comparing words and finding edges will take O(2 * total number of characters) = O(total number of characters).
Also, an edge is added when a mismatch is found. The maximum number of mismatches will be:
Overall time complexity is O(total number of characters + number of different characters + number of words) = O(total number of characters).
O(total number of characters).
Input takes O(total number of characters) space, and the graph we build takes O(number of different characters + number of words).