Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 19 Jul, 2020

Alien dictionary

Hard
Asked in companies
GoogleInfo Edge India (Naukri.com)Facebook

Problem statement

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

01 Approach

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.