大家好，我是 @负雪明烛。点击右上方的「+关注」↗，优质题解不间断！

题目大意

  1. 外星语也有 26 个英文字母组成，但是字母表顺序不是 "abc...xyz"而是重新排序后的 order。
    1. 比如order = "hlabcdefgijkmnopqrstuvwxyz"，那么 h是第一个字母，l是第二个字母…
  2. 现在给了一些外星语的单词 words，判断 words是不是外星语的字典序。

所谓字典序，以正常的英文字母表为例，见插图的解释：

解题方法

解密

这个外星语的题目，有点类似于凯撒密码：把字母表重新排列，根据映射关系就可以实现加密、解密。

本题中，order就相当于映射后的字母表，words就相当于加密后的密文。

我们可以根据映射关系，解密成以正常英文字母序表示的明文。

一般编程语言都实现了对英文字符串比较大小，我们直接使用。

  1. class Solution(object):
  2.     def isAlienSorted(self, words, order):
  3.         """
  4.         :type words: List[str]
  5.         :type order: str
  6.         :rtype: bool
  7.         """
  8.         mapping = dict()
  9.         for i, c in enumerate(order):
  10.             mapping[c] = i
  11.             decrypt = []
  12.             for word in words:
  13.                 decrypt.append("".join([chr(ord('a') + mapping[c]) for c in word]))     
  14.         return decrypt == sorted(decrypt)

复杂度

  • 时间复杂度：$O(M N + M log(M))$，953. 验证外星语词典 - 图1和 953. 验证外星语词典 - 图2分别是 words数组长度和平均的单词长度。
  • 空间复杂度：$O(N)$，映射了一份 words。

    总结

  1. 简单题，重要的是理解题意，按照题意去做就行。


我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。