Alien dictionary

Hard
0/120
Average time to solve is 46m
profile
Contributed by
303 upvotes
Asked in companies
SprinklrGoogleFacebook

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
3 1
a aa aaa
Sample Output 1 :
true
Explanation For Sample Output 1 :
The words are 'a', 'aa', and 'aaa'. Since the unique character here is 'a', the array to be returned will just be ['a']. 

The 'true' being printed signifies that the output returned by the function is valid.
Sample Input 2 :
3 3
caa aaa aab
Sample Output 2 :
true
Constraints :
1 ≤ N ≤ 300
1 ≤ K ≤ 26
1 ≤ Length of words ≤ 50

Time Limit: 1 sec
Hint

Try thinking around permutations and combinations! 

Approaches (2)
Permutations 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.
Time Complexity

O(K! * N * L), where K is the number of distinct characters, N is the number of words in the dictionary, and L is the maximum length of a word in the dictionary.

 

This is because we generate all possible permutations which costs K! operations for each word in the dictionary leading to a complexity of K! * N. Also, for each permutation we compare L characters which gives us an overall time complexity of K! * N * L.

Space Complexity

O(K) where K is the number of distinct characters

 

Since we are storing K distinct characters

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Alien dictionary
Full screen
Console