Alien dictionary

Posted: 19 Jul, 2020
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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

Example :
If the dictionary consists of the following words:-
["caa", "aaa", "aab"]
then, the order of alphabets are -
['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 an integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case or query contains an integer 'N' representing the size of the alien dictionary.

The second line contains 'N' single space-separated strings representing the words in the alien dictionary.
Output Format :
For each test case, return an array of characters representing the order in which they will appear in the alien language. The first element of the array shall represent the first letter of the alien language. The second one will represent the second letter of the language, so on and so forth. 

You do not need to print anything, just return the array of letters as they will appear in the language. 

Output for every test case will be printed in a separate line.
Note :
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 taken care of. Just implement the given functions.
Constraints :
1 <= t <= 100
0 <= N <= 10^5
0 <= Length of ARR[i] <= 10^5

Time Limit: 1 sec
Note :
The alien language consists of only lower case letters. However, their order might not be the same as the English language.
Approach 1

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.
Try Problem