953.验证外星语词典

953.验证外星语词典

Category	Difficulty	Likes	Dislikes
algorithms	Easy (55.37%)	169	-

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

---

Discussion | Solution

思路

按题意模拟即可，逐个字符根据字典序比较

解答

/*
 * @lc app=leetcode.cn id=953 lang=javascript
 *
 * [953] 验证外星语词典
 */

// @lc code=start
/**
 * @param {string[]} words
 * @param {string} order
 * @return {boolean}
 */
var isAlienSorted = function (words, order) {
  const map = {};
  for (let i = 0; i < order.length; i++) {
    const char = order[i];
    map[char] = i;
  }

  const isGreater = (word1, word2) => {
    if (word1 === word2) return false;

    let p = 0;
    while (p < word1.length && p < word2.length) {
      const char1 = word1[p],
        char2 = word2[p];
      const index1 = map[char1],
        index2 = map[char2];
      if (index1 > index2) {
        return true;
      } else if (index1 < index2) {
        return false;
      } else {
        p++;
      }
    }

    if (p < word1.length) return true;
    else return false;
  };

  for (let i = 0; i < words.length - 1; i++) {
    const word = words[i],
      nextWord = words[i + 1];
    if (isGreater(word, nextWord)) {
      return false;
    }
  }
  return true;
};
// @lc code=end