Problem of the day
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'.
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.
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.
3 1
a aa aaa
true
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.
3 3
caa aaa aab
true
1 ≤ N ≤ 300
1 ≤ K ≤ 26
1 ≤ Length of words ≤ 50
Time Limit: 1 sec
Try thinking around permutations and combinations!
Approach:
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.
O(K) where K is the number of distinct characters
Since we are storing K distinct characters