Alien Dictionary

Easy
0/40
Average time to solve is 10m
47 upvotes
Asked in companies
Thought WorksNagarro SoftwareTCS

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2 
3
word world row
worldabcefghijkmnpqstuvxyz
2
ninja codingninja
nabcdefghijklmopqrstuvwxyz
Sample Output 1:
NO
YES
Explanation of sample input 1:
For the first test case,

The first and Second words of ‘WORDS’ are not lexicographically sorted as ‘l’ comes before ‘d’ in the alien language. Hence, the answer is ‘NO’.


For the second test case:
The words of ‘WORDS’ are sorted in lexicographical order according to the alien language. Hence, the answer is ‘YES’.
Sample Input 2:
2
6
bg poeupcym i yqifzvlcp d cnjodzbq 
gxqynrktahwoevljizmbdspfcu
7
kt ggt lmvynuw dnvsxjy fht qeefx ovs 
ykarxuhvimjgldpfqtzsebownc
Sample Output 2:
NO
YES
Hint

Check the adjacent words.

Approaches (2)
Comparing adjacent words.

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 INORDER is true:
      • Continue.
    • If length of WORDS[i] > length of WORDS[i+1]:
      • Mismatch in lexicographical order.
      • Return ‘FALSE’.
  • Return ‘TRUE’.
Time Complexity

O(W), where ‘W’ total number of letters in ‘WORDS’ array.

 

In this approach, we are iterating through each word of ‘WORDS’ array to check whether they are arranged in lexicographical order or not.Hence,the overall time complexity is O(W).

Space Complexity

O(1).

 

In this approach, we are using an auxiliary space of size 26 to store the rank of each letter. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Alien Dictionary
Full screen
Console