953. Verifying an Alien Dictionary
In an alien language, surprisingly they also use English lowercase letters, but possibly in a different
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.
Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.
Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Explanation: As 'd' comes after 'l' in this language, then words > words, hence the sequence is unsorted.
Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
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.
- 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.
- 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.
- 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.
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
if (len(words) <= 1):
if(dict_let[words[pointer]] < dict_let[words[pointer]]):
pointer = 0
elif(dict_let[words[pointer]] > dict_let[words[pointer]]):
pointer += 1
if pointer == len(words):
elif pointer == len(words):
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.
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.