Verifying an Alien Dictionary — Day 39(Python)

Image for post
Image for post
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:

Example 2:

Example 3:

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.

  1. The character at the pointer position for 1st word is smaller than 2nd word. In that case, we can pop that word from our list, because it satisfies our lexicographical arrangement.
  2. The character at the pointer position for 1st word is greater than 2nd word. In that case, we should be returning False, because the condition of lexicography is not satisfied.
  3. If the characters are the same for both the words, we keep incrementing the value of the pointer until there is a difference or one of the words is completed. If word2 completes before word1, return False. Else continue with comparison.

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

Let us check the code snippet.

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