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

Output :

Explanation of given Test Cases :

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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!