python - 通过 73/115 个测试用例 : Verifying an Alien dictionary

Question

问。给定用外来语言编写的单词序列以及字母表顺序，当且仅当给定单词在此外语中按字典顺序排序时返回 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”跳过这种情况。这可以防止程序返回误报，因为即使字典中前面有其他单词的顺序不正确，它也可能返回“true”:

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

该解决方案已被接受。