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 lexicographicaly 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.
Constraints:
1 <= words.length <= 1001 <= words[i].length <= 20order.length == 26words[i] and order are English lowercase letters.
Description taken from https://leetcode.com/problems/verifying-an-alien-dictionary/.
#O(N) Time, where N is the count of characters in all words.#O(1) Spaceclass Solution: def isAlienSorted(self, words: List[str], order: str) -> bool: alien = {} for index, char in enumerate(order): alien[char] = index for i in range(len(words) - 1): word_one = words[i] word_two = words[i+1] difference = False for char in range(min(len(word_one), len(word_two))): if word_one[char] != word_two[char]: difference = True if alien[word_one[char]] > alien[word_two[char]]: return False else: break if len(word_one) > len(word_two) and not difference: return False return TrueWhenever we are translating one value to another, whether it be an order of words or numbers, it may be a good idea to map the translations for easy access.
What we can do is iterate through the order string and map each character to the index it resides in, creating an order reference we can easily utilize for comparison between two characters. Then, we can iterate through the words array and compare the characters of each word with the word directly after it. If the first word has a greater ordering according to our alien dictionary, then we will return false.
One tricky thing we need to look out for is null values, for example when we see "apple" and "app", this should be false because a null value has a lesser ordering than any other character. This is us making an assumption that aliens handle the lexicographical sorting of blank letters the same as humans do, perhaps. In any case, to handle test cases such as these, we will ensure that we found a difference between the two strings before we mark that the sorting is correct. If we found no difference between both words' characters and the first word was longer than the second word, then the sorting is incorrect due to the null values of the second word.
Let's start by initializing our alien dictionary, Python pun intended.
alien = {}
We will then enumerate through the order string and map each character to the index it was found in. An enumeration is a traversal through values while keeping a counter.
This is similar to if we were given a string of our human, English alphabet, "A" would be one, "B" would be two, etc.
for index, char in enumerate(order): alien[char] = index
Next, we will begin iterating through the words array and comparing two words at a time, the current word and the next word.
for i in range(len(words) - 1): word_one = words[i] word_two = words[i+1]
As mentioned previously, we will need a flag to check that there was a difference found in the scenario where we have word one being longer than word two, but there was no difference in characters so the null characters hold precedence over the remaining characters in the first word, this would be like "apple" and "app".
difference = False
Next, we will begin iterating through the characters of both words. We will choose to iterate up to the last character of the shorter word so that we don't get an index out-of-bounds error during the comparison.
for char in range(min(len(word_one), len(word_two))):
Let's first check if the characters are different to handle the null character edge case.
if word_one[char] != word_two[char]: difference = True
If they are different, we can check the ordering between them.
If according to our alien dictionary, the ordering of the current character in the second word is greater than the current character in the first word, then these two words are out of order so we will return false.
if alien[word_one[char]] > alien[word_two[char]]: return False
If that is not the case, then the ordering of the current character in the first word is lesser than the current character in the second word so we will break because we just need to verify that the first different character between the current word and the next word has a lower order.
If we had "sniffle" and "snivel", in our English dictionary, it doesn't matter what comes after the "f" and the "v", as long as the word with the "f" comes before the other, so we can stop comparing characters after we find that these two letters have the correct ordering.
else: break
If we have gone through all the characters in the smaller word and have not found a difference between it and the characters in the larger word, we will check the length of the words. If the length of the first word is larger than the second word, that means the second word has null characters that are smaller than the remaining characters in the first word and makes it unsorted, as mentioned previously.
if len(word_one) > len(word_two) and not difference: return False
If we have traversed each word and never returned false, then all the words were sorted correctly.
return True