Получение тестовых случаев 73/115: Проверка словаря инопланетян

Question

Q. Учитывая последовательность слов, написанных на иностранном языке, и порядок алфавита, верните true, если и только если данные слова отсортированы лексикографически на этом иностранном языке. Ниже приведены некоторые примеры:

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.

Моим решением было следующее:

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

почему этим проходит только 73/115 тестовых случаев?

Answer 1

Я нашел ответ на свой вопрос. Вместо возврата true в случае, когда порядок символа предыдущего слова меньше, чем порядок слова после этого слова, вы должны пропустить этот случай, используя «break». Это не позволяет программе возвращать ложное срабатывание, поскольку она может возвращать «истину», даже если впереди в словаре есть другие слова, которые не в правильном порядке:

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

Это решение было принято.

Answer 2

Сделано несколько изменений в вашем алгоритме, пожалуйста, проверьте, работает ли это

    def isAlienSorted(self, words, order):
        orderDict = {}
        for index, char in enumerate(order):
            orderDict[char] = index

        for j in range(len(words)-1):
            isCheck = True
            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]]:
                    isCheck = False
                    break
            if isCheck and len(words[j]) > len(words[j+1]):
                return False

        return True