获得 73/115 个测试用例通过：验证 Alien 字典

Question

问。给定一个用外星语言书写的单词序列和字母表的顺序，当且仅当给定的单词以这种外星语言按字典顺序排序时，return 为真。以下是一些示例：

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

我找到了问题的答案。在前一个单词的字符顺序小于该单词后的单词顺序的情况下，不要 return 为真，您应该使用 'break' 跳过这种情况。这可以防止程序 return 误报，因为它可能 return '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

此解决方案已被接受。

获得 73/115 个测试用例通过：验证 Alien 字典

Getting 73/115 testcases passed: Verifying an Alien dictionary

python

data-structures

testcase