Verifying an Alien Dictionary — Day 39(Python)

Photo by Erik Mclean on Unsplash

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: true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

Example 2:

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

Example 3:

Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: 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[0][pointer]] < dict_let[words[1][pointer]]):
words.pop(0)
pointer = 0
elif(dict_let[words[0][pointer]] > dict_let[words[1][pointer]]):
return False
else:
pointer += 1
if pointer == len(words[0]):
words.pop(0)
elif pointer == len(words[1]):
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.

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

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store