通过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

您的算法进行了少量更改，请检查是否可行

    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

Answer 2

我找到了问题的答案。如果前一个单词的字符顺序小于该单词后的单词顺序，则不要返回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

此解决方案已被接受。