验证外星语词典

难度: 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 中的所有字符都是英文小写字母。

Submission

运行时间: 25 ms

内存: 0.0 MB

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        d = {}
        for i in range(len(order)):
            d[order[i]] = i
        

        for i in range(len(words) - 1):
            p,q = 0,0

            while p < len(words[i]) and q < len(words[i + 1]):
                if words[i][p] != words[i+1][q]:
                    break
                p += 1
                q += 1

            if p == len(words[i]) or q == len(words[i+1]):
                if len(words[i+1]) < len(words[i]):
                    return False
            else:
                c1, c2 = words[i][p], words[i+1][q]
                if d[c1] > d[c2]:
                    return False
        
        return True

Explain

首先，这个解法通过建立一个哈希表来映射每个字符在外星语言中的索引，这样可以快速比较任意两个字符的顺序。接着，算法逐对比较相邻的单词，检查它们是否按照外星语言的字典顺序排列。对于每一对单词，从左到右比较每个字符，直到找到第一对不相同的字符或者其中一个单词先结束。如果找到不同的字符，就比较它们的顺序；如果没有找到不同的字符，就检查更短的单词是否排在前面（即确保不会出现长单词排在短单词之前的情况）。任何一次比较如果发现顺序错误，就立即返回false。如果所有的单词都检查完毕，没有发现问题，则返回true。

时间复杂度: O(m * k)

空间复杂度: O(1)

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        # 建立外星语言中字符与其索引的映射关系
        d = {}
        for i in range(len(order)):
            d[order[i]] = i
        
        # 比较相邻的单词
        for i in range(len(words) - 1):
            p, q = 0, 0
            # 逐字符比较直到出现不同字符或者一个单词结束
            while p < len(words[i]) and q < len(words[i + 1]):
                if words[i][p] != words[i+1][q]:
                    break
                p += 1
                q += 1
            
            # 检查是否因为一个单词结束而停止比较
            if p == len(words[i]) or q == len(words[i+1]):
                # 确保不是因为更长的单词排在更短的单词前面
                if len(words[i+1]) < len(words[i]):
                    return False
            else:
                # 比较找到的第一对不同的字符
                c1, c2 = words[i][p], words[i+1][q]
                if d[c1] > d[c2]:
                    return False
        
        return True

Explore

在构建哈希表时，通过遍历外星语言的字符顺序字符串 `order`，并利用循环的索引 `i`，可以确保每个字符的正确索引被记录。对于每个字符 `order[i]`，哈希表 `d` 的键是字符本身，值是该字符对应的索引 `i`。这样，每个字符都会根据其在字符串 `order` 中的位置被映射到一个唯一的整数索引上。

当比较两个单词的字符时，如果当前字符相同，算法会继续递增两个单词的索引 `p` 和 `q`，以便比较下一个字符。这个过程持续进行，直到发现第一对不同的字符或者其中一个单词的字符已全部比较完毕。这种方法确保了只有在找到明确的字典序差异或确认一个单词为另一个单词的前缀时才停止比较。

当较短的单词的所有字符都已经与较长单词的对应部分比较完毕且相同后，需要检查两个单词的长度以判断它们的字典序。这是因为如果较长的单词以较短的单词为前缀，则按字典序，较短的单词应该排在较长的单词之前。如果较短的单词排在较长的单词后面，则表示单词顺序错误，因此返回 false。

如果在比较过程中发现较短单词排在较长单词前面，而且较短的单词是较长单词的前缀，则这实际上是正确的字典序排列，应返回 true。但如果较长的单词以较短的单词为前缀且排在较短的单词之前，则这违反了字典序的规则，因此会返回 false。字典序的确定是基于单词的相对位置和长度来判断的。