跳到主要内容

953.验证外星语词典

· 阅读需 4 分钟

1、题干​

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

解题思路​

思路 将words中的所有字符替换为正常字典序的字符，然后使用比较运算符（大于号、小于号等）去比较所有words即可。

例子 words = ["hl","la"], order = "hlabcdefgijkmnopqrstuvwxyz"

  • 将words中的字符替换为正常字典序的字符，结果为：words = ["ab","bc"]
  • 使用比较运算符比较所有words，"ab"<"bc"结果为true，最终返回true

步骤

  • 创建哈希映射map，遍历order，获得外星字典序（键）与正常字典序（值）的映射
  • 遍历words中的所有字符串
    • 将words[i]中的字符替换为正常字典序的字符
    • 使用比较运算符比较words[i]与words[i - 1]的大小
    • 如果i && words[i] < words[i - 1]则不符合外星字典序直接返回false
  • 函数运行到结尾，则说明符合外星字典序，返回true

代码​

var isAlienSorted = function (words, order) {
    const map = new Map();
    for (let i = 0; i < order.length; i++) map.set(order[i], String.fromCharCode(97 + i));

    for (let i = 0; i < words.length; i++) {
        words[i] = [...words[i]].reduce((a, c) => a + map.get(c), '');
        if (i && words[i] < words[i - 1]) return false;
    }

    return true;
};