验证外星语词典

难度: Easy

某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。

给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

示例 1：

输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
输出：true
解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。

示例 2：

输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
输出：false
解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。

示例 3：

输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
输出：false
解释：当前三个字符 "app" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 "apple" > "app"，因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（更多信息）。

提示：

1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
在 words[i] 和 order 中的所有字符都是英文小写字母。

注意：本题与主站 953 题相同： https://leetcode-cn.com/problems/verifying-an-alien-dictionary/

Submission

运行时间: 24 ms

内存: 16.1 MB

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:

        order = {c: i for i, c in enumerate(order)}

        def less(w1, w2):
            for i in range(len(w1)):
                if i >= len(w2) or order[w1[i]] > order[w2[i]]:
                    return False
                if order[w1[i]] < order[w2[i]]:
                    return True
            return True
        
        for i in range(1, len(words)):
            if not less(words[i-1], words[i]):
                return False
        return True

Explain

此题解首先将外星语字母表的顺序转换成一个字典，其中每个字母对应一个索引，表示其在字母表中的位置。然后定义一个辅助函数`less`来比较两个单词在外星语中的字典序。对于每一对相邻的单词，使用`less`函数进行比较，确保前一个单词在字典序上小于或等于后一个单词。如果发现任何一对单词不符合这一条件，则立即返回`false`。如果所有相邻单词都符合条件，则返回`true`。

时间复杂度: O(N*L)

空间复杂度: O(1)

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:

        # 将字母表按给定顺序映射到字典中，其中字典的键为字母，值为该字母的索引
        order = {c: i for i, c in enumerate(order)}

        # 辅助函数，用于比较两个单词的外星语字典序
        def less(w1, w2):
            for i in range(len(w1)):
                # 如果第一个单词比第二个长，或者在某个位置上第一个单词的字符大于第二个单词的字符
                if i >= len(w2) or order[w1[i]] > order[w2[i]]:
                    return False
                # 如果在某个位置上第一个单词的字符小于第二个单词的字符
                if order[w1[i]] < order[w2[i]]:
                    return True
            # 如果两个单词相等或者第一个单词比第二个短且其余字符相同
            return True
        
        # 迭代比较相邻的两个单词
        for i in range(1, len(words)):
            if not less(words[i-1], words[i]):
                return False
        return True

Explore

在这种情况下，如果较短的单词（例如'abc'）是较长单词（例如'abcd'）的前缀，并且在较短单词结束时没有发现任何字典序冲突，则较短的单词被认为是小于较长的单词。这是因为在外星语字典排序中，当一个单词是另一个单词的前缀时，没有更多的字符可以比较，所以较短的单词自然小于较长的单词。在题解的`less`函数中，如果遍历完较短单词的所有字符后，两个单词都没有违反字典序，则会返回`True`，表示第一个单词小于或等于第二个单词。

如果输入的order字符串包含重复的字符，这将导致在建立字母与索引映射时出现问题，因为字典结构要求每个键（字母）对应唯一的值（索引）。这种情况在题解中并未直接处理，可能需要在实现前增加检查以确保输入的order是有效的，并且每个字符只出现一次。如果order不足26个字符，这可能意味着并非所有字母都有映射，这将影响字母表的完整性和字典序比较的正确性。理想情况下，order应包含目标语言中的所有字符，且每个字符只出现一次。

在`less`函数中，如果第一个单词结束但第二个单词尚未结束的情况下直接返回`True`，是基于假设较短的单词在没有其他违反字典序的字符的情况下自然小于较长的单词。这是因为较短的单词是较长单词的前缀，按照字典序规则，较短的单词确实应视为小于较长的单词。这种处理方式是合理的并符合外星语字典序的比较逻辑。