Last Updated: 19 Jul, 2020
Alien dictionary
Hard
Asked in companies
You have been given a sorted (lexical order) dictionary of an alien language.
Write a function that returns the order of characters as a string in the alien language. This dictionary will be given to you as an array of strings called 'dictionary', of size 'N'.
Example :
If the dictionary consists of the following words:-
["caa", "aaa", "aab"], and 'K' is 3.
Then, the order of the alphabet is -
['c', 'a', 'b']
Note:
If the language consists of four letters, the four letters should be the starting four letters of the English language.
However, their order might differ in the alien language.
Input format :
The first line contains two integers, 'N' and 'K', representing the alien dictionary's size and the standard dictionary's initial alphabet.
The second line contains 'N' single space-separated strings representing the words in the alien dictionary.
Output Format :
If your order is correct, the output will be true. Otherwise, it will be false.
Note:
You do not need to print anything; it has already been handled. Just implement the given functions.
Approaches
Approach:
- Find all the distinct characters present in all the words.
- Generate all permutations of these distinct characters.
- Treat each of the permutations as a correct sequence of alphabets. Now check if the given words are sorted according to this sequence. In order to do this, we will:-
- For all words from 1 to n - 1, let the current word be ‘currWord’ and the next word be ‘nextWord’.
- One by one compare characters of both words and find the first mismatching character. In case there was no mismatching character, we continue to the next word.
- Let us say that the mismatching characters were ‘ch1’ and ‘ch2’ in ‘currWord’ and ‘nextWord’ respectively.
- Now, if these words(currWord and nextWord) follow the dictionary, ‘ch1’ will occur before ‘ch2’ in the sequence.
- In case the words are sorted according to the current sequence, we will return this sequence.
Approach: 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!
Hence,
- 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.