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.’

Given

3
a aa aaa

Output :

True

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.

Approach :

Topological Sort

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.

Time Complexity: O(N+K)
Space Complexity: O(K)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.