# Verifying an Alien Dictionary — Day 39(Python)

Today’s question is a common question among Facebook interviewers. Let us look into the question without wasting much time.

953. Verifying an Alien Dictionary

In an alien language, surprisingly they also use English lowercase letters, but possibly in a different `order`. The `order` of the alphabet is some permutation of lowercase letters.

Given a sequence of `words` written in the alien language, and the `order` of the alphabet, return `true` if and only if the given `words` are sorted lexicographically in this alien language.

Example 1:

`Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"Output: trueExplanation: As 'h' comes before 'l' in this language, then the sequence is sorted.`

Example 2:

`Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"Output: falseExplanation: As 'd' comes after 'l' in this language, then words > words, hence the sequence is unsorted.`

Example 3:

`Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"Output: falseExplanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).`

The first thought that came into my mind after looking into this question was to create a dictionary that can help us to keep track of lexicographical order according to the alien dictionary.

To check if the list is arranged in lexicographical order, we need to check if adjacent words are ordered lexicographically. For checking if the adjacent words are lexicographical, we can use a pointer. The pointer should check if each character is arranged according to the dictionary given.

There are 3 cases to consider, which are as follows.

If the words are arranged according to the dictionary, then we have to return True.

Let us check the code snippet.

`class AlienSortChecker:    def isAlienSorted(self, words: List[str], order: str) -> bool:        pos = 0        dict_let = collections.defaultdict(int)        for i in order:            dict_let[i] = pos            pos += 1        pointer = 0        while(words):            if (len(words) <= 1):                return True            if(dict_let[words[pointer]] < dict_let[words[pointer]]):                words.pop(0)                pointer = 0            elif(dict_let[words[pointer]] > dict_let[words[pointer]]):                return False            else:                pointer += 1                if pointer == len(words):                    words.pop(0)                elif pointer == len(words):                    return False        return True`

Complexity analysis.

Time Complexity

We are trying to check for each character for each word. Hence the Time Complexity if O(N*M) where N is the number of words and M represents the length of the words.

Space Complexity.

We are not using any extra data structure to store anything. Hence the space complexity is O(1).

I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.

## More from Annamariya Tharayil

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt