953.验证外星语词典

验证外星语词典

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

给定一组字符串 words，根据字典顺序判断这些字符串是否有序。

示例 1:

输入：words = [“hello”,”leetcode”], order = “hlabcdefgijkmnopqrstuvwxyz”
输出：true

示例 2:

输入：words = [“word”,”world”,”row”], order = “worldabcefghijkmnpqrstuvxyz”
输出：false

提示:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 20
• order.length == 26
• order 中的所有字符都互不相同

解析

建立字符到索引的映射，然后逐个比较相邻字符串。

var isAlienSorted = function (words, order) {
  const map = {};
  for (let i = 0; i < order.length; i++) {
    map[order[i]] = i;
  }

  for (let i = 1; i < words.length; i++) {
    if (!compare(words[i - 1], words[i], map)) {
      return false;
    }
  }
  return true;
};

function compare(a, b, map) {
  const len = Math.min(a.length, b.length);
  for (let i = 0; i < len; i++) {
    if (a[i] !== b[i]) {
      return map[a[i]] <= map[b[i]];
    }
  }
  return a.length <= b.length;
}

时间复杂度 O(N * L)，空间复杂度 O(1)。