Alien Dictionary
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

Question

Alien Dictionary

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

Accepted Answer

The task is to check whether the given words are sorted lexicographically in an alien language.

Read the number of test cases
For each test case, read the number of words, the words themselves, and the order string
Check if the words are sorted lexicographically based on the given order string
Print 'YES' if the words are sorted, else print 'NO'

Accepted Answer

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

Space Complexity: O(1)Explanation:

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

Time Complexity: OtherExplanation:

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

Java (SE 1.8)


/*
    Time Complexity: O(W)
    Space Complexity: O(1)

    where W total number of letters in WORDS array.
*/
public class Solution {

	public static Boolean alienDictonary(int n, String words[], String orders) {

		char order[] = orders.toCharArray();
		int rank[] = new int[26];
		for (int i = 0; i < 26; i++) {
			rank[i] = 0;
		}

		for (int i = 0; i < 26; i++) {
			rank[(int) (order[i] - 'a')] = i;
		}

		for (int i = 0; i < n - 2; i++) {

			int j = 0;
			Boolean inorder = false;

			while (j < words[i].length() && j < words[i + 1].length()) {
				char w[] = words[i].toCharArray();
				char w1[] = words[i + 1].toCharArray();

				if (rank[(int) (w[j] - 'a')] > rank[(int) (w1[j] - 'a')]) {
					// Mismatch in lexicological order.
					return false;
				}

				if (rank[(int) (w[j] - 'a')] < rank[(int) (w1[j] - 'a')]) {

					inorder = true;
					break;
				}

				j = j + 1;
			}

			if (inorder) {
				// Adjacent words are in correct order.
				continue;
			}

			if (words[i].length() > words[i + 1].length()) {
				return false;
			}
		}

		return true;
	}
}

C++ (g++ 5.4)

/*
    Time Complexity: O(W)
    Space Complexity: O(1)

    where ‘W’ total number of letters in ‘WORDS’ array.
*/

bool alienDictonary(int n, vector &words, string &order)
{
    vector rank(26, 0);

    for(int i = 0; i < 26; i++){
        rank[order[i] - 'a'] = i;
    }

    for(int i = 0; i < n-2; i++){
    
        int j = 0;
        bool inorder = false;

        while ( j < words[i].size() && j < words[i+1].size()){

            if (rank[words[i][j] - 'a'] > rank[words[i+1][j]- 'a']){
                // Mismatch in lexicological order.
                return false;
            }

            if (rank[words[i][j] - 'a'] < rank[words[i+1][j]- 'a']){

                inorder = true;
                break;
            }

            j = j + 1;
        }

        if (inorder){
            // Adjacent words are in correct order.
            continue;
        }

        if ( words[i].size() > words[i+1].size()){
            return false;
        }
    }

    return true;
}

Python (3.5)

"""

    Time Complexity: O(W)

    Space Complexity: O(1)



    where ‘W’ total number of letters in ‘WORDS’ array.

"""



from typing import *





def alienDictonary(n: int, words: List[str], order: str) -> bool:



    rank = [0]*26



    for i in range(26):

        rank[ord(order[i])-ord('a')] = i



    for i in range(n-2):



        j = 0

        inorder = False



        while j < len(words[i]) and j < len(words[i+1]):



            if rank[ord(words[i][j]) - ord('a')] > rank[ord(words[i+1][j]) - ord('a')]:

                # Mismatch in lexicological order.

                return False



            if rank[ord(words[i][j]) - ord('a')] < rank[ord(words[i+1][j]) - ord('a')]:



                inorder = True

                break



            j = j + 1



        if inorder:

            # Adjacent words are in correct order.

            continue



        if len(words[i]) > len(words[i+1]):

            return False



    return True

Accepted Answer

Transform each word.

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.