题目

某种外星语也使用英文小写字母，但可能顺序 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 中的所有字符都是英文小写字母。

思路

字符串匹配问题，我的思路是先将给定词典规则放入哈希表中准备，然后遍历所有给定数组中的字符串，将每个字符串与后面一个字符串逐个字符比较，判断是否符合哈希表中的规则。

具体比较细节：

1.比较是按照两者字符串长度较短的长度进行的，不然会下标溢出

2.比较有四种情况

①前面字符串的字符小于后面字符串，说明前面字符串符合规则，到下一字符串比较

②前面字符串的字符大于后面字符串，说明前面的字符串不符合规则，直接返回False

③前面字符串的字符等于后面字符串，继续向下比较

④前面字符串的长度大于后面字符串的情况，该情况如果前面比较未返回False说明该字符串前n个字符等于后面只有n个字符的字符串，即出现["apple","app"]这种情况，我们需要另外考虑这种情况，判断比较的长度n是否等于前方字符串的长度，并且判断前方字符串的前n个字符是否都和后方字符串的字符相等

代码

def isAlienSorted(words: List[str], order: str) -> bool:
  # 哈希表记录规则
    res = {}
    for i in range(len(order)):
        res[order[i]] = i
    for i in range(len(words) - 1):
      # 判断前方字符串的前n个字符是否都等于后方字符串的字符
        judge = 0
        n = min(len(words[i]), len(words[i+1]))
        for j in range(n):
          # 情况①
            if res.get(words[i][j]) < res.get(words[i+1][j]):
              # 修改判断，此种情况符合规则
                judge = 1
                break
            # 情况②
            elif res.get(words[i][j]) > res.get(words[i+1][j]):
                return False
            # 情况③
            else:
                continue
         # 情况④，只有前方字符串长于后方字符串以及二者前n个字符都相等的情况返回False
        if n != len(words[i]) and judge == 0:
            return False
    return True