Alien dictionary — Asked in Adobe and Facebook Interviews
Problem Statement :
You have been given a sorted (lexical order) dictionary of an alien language. Write a function that finds the order of characters in the alien language. This dictionary will be given to you in the form of an array of strings called ‘dictionary,’ of size ‘N.’
a aa aaa
Explanation of given Test Cases :
For the test case, the words are 'a', 'aa', and 'aaa'. Since the only unique character here is 'a', so the array to be returned will just be ['a']. The 'true' that is being printed just signifies that the output returned by the function is valid.
Here, if we consider [“wrt”, “wrf”, ….] the first two of the words of the alien dictionary then by looking at the first mismatch in the characters tells us vital information on the order they occur!
That means, in from the above two words, we can say ‘t’ comes before ‘f’! We can denote this relation by, ‘t’ → ‘f’.
We can represent this relation using a directed graph!
- Iterate over all the words and make the graph representing the above relation. All the distinct characters will be the vertices of the graph whereas, the relation, mapping which character comes before another character will be the directed edge.
- Do a Topological Sort over the built graph and return one of the possible orders for the same.
Time Complexity: O(N+K)
Space Complexity: O(K)