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

## Problem statement

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