Q. 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. Following are some examples:
Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.
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.
Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: The first three characters "app" match, and the second string is shorter (in size.
The following was my solution:
class Solution(object):
def isAlienSorted(self, words, order):
orderDict = {}
for index, char in enumerate(order):
orderDict[char] = index
for j in range(len(words)-1):
for i in range(min(len(words[j]),len(words[j+1]))):
word1 = words[j]
word2 = words[j+1]
if orderDict[word1[i]] == orderDict[word2[i]]:
continue
if orderDict[word1[i]] > orderDict[word2[i]]:
return False
if orderDict[word1[i]] < orderDict[word2[i]]:
return True
if len(words[j]) > len(words[j+1]):
return False
return True
why are only 73/115 test cases being passed by this?
I found the answer to my question. Instead of returning true in the case where the order of the character of the preceding word is lesser than the order of the word after that word, you should skip that case, by using 'break'. This prevents the program from returning a false positive, since it might return 'true' even if there are other words ahead in the dictionary which are not in the correct order:
def isAlienSorted(self, words, order):
orderDict = {}
for index, char in enumerate(order):
orderDict[char] = index
for j in range(len(words)-1):
word1 = words[j]
word2 = words[j+1]
for i in range(min(len(word1),len(word2))):
if orderDict[word1[i]] != orderDict[word2[i]]:
if orderDict[word1[i]] > orderDict[word2[i]]:
return False
break
elif len(word1) > len(word2):
return False
return True
This solution was accepted.