Last Updated: 6 Dec, 2021
Alien Dictionary
Easy
Asked in companies
Ninja is learning a new but strange language known as Alien Language. Alien language possesses the same alphabets as of English language, but their order is different. The order of letters are given as ‘ORDER’ string. Ninja has ‘N’ words in the ‘WORDS’ array. Ninja’s task is to check whether the words of ‘WORDS’ are sorted lexicographically in this alien language or not.
Note: ‘ORDER’ consists of all 26 letters of English alphabet.
For Example
If ‘WORDS’ = ["word","world","row"], ‘ORDER’ = "worldabcefghijkmnpqstuvxyz",the answer will be ‘NO’ as first and second words are not lexicographically sorted as ‘l’ comes before ‘d’ in alien language.
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains a single integer, ‘N’ denoting the number of words.
The second line of each test case contains ‘N’ strings corresponding to ‘WORDS’.
The third line contains a permutation of 26 letters denoting the ‘ORDER’ string.
Output Format:
For each test case, print ‘YES’ if the words are sorted, else print ‘NO’.
Print the output of each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 1000.
1 <= length of ‘WORDS[i]’ <= 20
Time limit: 1 sec
Approaches
To check the lexicographical order, we will check that if the adjacent words are in the correct order or not. We will first store the rank of each letter of alien language in an array ‘RANK’.
If the rank of ‘A’ is greater than the rank of ‘B’ it implies A comes after B in the alien language.
We will iterate through the ‘ORDER’ string and set the RANK[ORDER[i]] as i.
Now, we will compare the two adjacent words and if we found any mismatch in the order, return ‘FALSE’.
Else, return ‘TRUE’
Algorithm:
- Declare ‘RANK’ array of size 26 to store the rank of each letter of alien language.
- For i in range 0 to 25:
- Set RANK[ORDER[i] - ‘a’] as i.
- For i in range 0 to N-2:
- Set j =0
- While j<length of WORDS[i] and j < length of WORDS[i+1]:
- If RANK[WORDS[i][j]] > RANK[WORDS[i+1][j]] :
- Rank of letter of first word is greater than rank of letter of second word.
- Mismatch in lexicographical order.
- Return ‘FALSE’.
- If RANK[WORDS[i][j]] < RANK[WORDS[i+1][j]] :
- Words in order.
- Set INORDER as TRUE.
- Break.
- Set j as j+1.
- If RANK[WORDS[i][j]] > RANK[WORDS[i+1][j]] :
- If INORDER is true:
- Continue.
- If length of WORDS[i] > length of WORDS[i+1]:
- Mismatch in lexicographical order.
- Return ‘FALSE’.
- Return ‘TRUE’.
In this approach,we will first transform each word of ‘WORDS’ according to the rank of the letter in Alien language.
For example, if the ‘ORDER’ string is “worldabcefghijkmnpqstuvxyz”,so all the ‘w’ in ‘WORDS’ will be transformed into ‘a’ , all the ‘o’ will be transformed into ‘b’, and so on.
After transformation, we can check the lexicographical order of adjacent words using simple <,> operators.
Algorithm:
- Declare ‘RANK’ array of size 26 to store the rank of each letter of alien language.
- For i in range 0 to 25:
- Set RANK[ORDER[i] - ‘a’] as i.
- For i in range 0 to N-1:
- For j in range 0 to length of WORDS[i]-1:
- Set WORDS[i][j] as RANK(WORDS[i][j]) + ‘a’.
- For j in range 0 to length of WORDS[i]-1:
- For i in range 0 to N-2:
- If WORDS[i] > WORDS[i+1]:
- Mismatch in lexicographical order.
- Return ‘FALSE’.
- If WORDS[i] > WORDS[i+1]:
- Return ‘TRUE’.