Question

953. 验证外星语词典

English Version

题目描述

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

解法

方法一

class Solution:
  def isAlienSorted(self, words: List[str], order: str) -> bool:
    m = {c: i for i, c in enumerate(order)}
    for i in range(20):
      prev = -1
      valid = True
      for x in words:
        curr = -1 if i >= len(x) else m[x[i]]
        if prev > curr:
          return False
        if prev == curr:
          valid = False
        prev = curr
      if valid:
        return True
    return True

class Solution {
  public boolean isAlienSorted(String[] words, String order) {
    int[] m = new int[26];
    for (int i = 0; i < 26; ++i) {
      m[order.charAt(i) - 'a'] = i;
    }
    for (int i = 0; i < 20; ++i) {
      int prev = -1;
      boolean valid = true;
      for (String x : words) {
        int curr = i >= x.length() ? -1 : m[x.charAt(i) - 'a'];
        if (prev > curr) {
          return false;
        }
        if (prev == curr) {
          valid = false;
        }
        prev = curr;
      }
      if (valid) {
        break;
      }
    }
    return true;
  }
}

class Solution {
public:
  bool isAlienSorted(vector<string>& words, string order) {
    vector<int> m(26);
    for (int i = 0; i < 26; ++i) m[order[i] - 'a'] = i;
    for (int i = 0; i < 20; ++i) {
      int prev = -1;
      bool valid = true;
      for (auto& x : words) {
        int curr = i >= x.size() ? -1 : m[x[i] - 'a'];
        if (prev > curr) return false;
        if (prev == curr) valid = false;
        prev = curr;
      }
      if (valid) break;
    }
    return true;
  }
};

func isAlienSorted(words []string, order string) bool {
  m := make([]int, 26)
  for i, c := range order {
    m[c-'a'] = i
  }
  for i := 0; i < 20; i++ {
    prev := -1
    valid := true
    for _, x := range words {
      curr := -1
      if i < len(x) {
        curr = m[x[i]-'a']
      }
      if prev > curr {
        return false
      }
      if prev == curr {
        valid = false
      }
      prev = curr
    }
    if valid {
      break
    }
  }
  return true
}

function isAlienSorted(words: string[], order: string): boolean {
  const map = new Map();
  for (const c of order) {
    map.set(c, map.size);
  }
  const n = words.length;
  for (let i = 1; i < n; i++) {
    const s1 = words[i - 1];
    const s2 = words[i];
    const m = Math.min(s1.length, s2.length);
    let isEqual = false;
    for (let j = 0; j < m; j++) {
      if (map.get(s1[j]) > map.get(s2[j])) {
        return false;
      }
      if (map.get(s1[j]) < map.get(s2[j])) {
        isEqual = true;
        break;
      }
    }
    if (!isEqual && s1.length > s2.length) {
      return false;
    }
  }
  return true;
}

use std::collections::HashMap;
impl Solution {
  pub fn is_alien_sorted(words: Vec<String>, order: String) -> bool {
    let n = words.len();
    let mut map = HashMap::new();
    order
      .as_bytes()
      .iter()
      .enumerate()
      .for_each(|(i, &v)| {
        map.insert(v, i);
      });
    for i in 1..n {
      let s1 = words[i - 1].as_bytes();
      let s2 = words[i].as_bytes();
      let mut is_equal = true;
      for i in 0..s1.len().min(s2.len()) {
        if map.get(&s1[i]) > map.get(&s2[i]) {
          return false;
        }
        if map.get(&s1[i]) < map.get(&s2[i]) {
          is_equal = false;
          break;
        }
      }
      if is_equal && s1.len() > s2.len() {
        return false;
      }
    }
    true
  }
}

#define min(a, b) (((a) < (b)) ? (a) : (b))

bool isAlienSorted(char** words, int wordsSize, char* order) {
  int map[26] = {0};
  for (int i = 0; i < 26; i++) {
    map[order[i] - 'a'] = i;
  }
  for (int i = 1; i < wordsSize; i++) {
    char* s1 = words[i - 1];
    char* s2 = words[i];
    int n = strlen(s1);
    int m = strlen(s2);
    int len = min(n, m);
    int isEqual = 1;
    for (int j = 0; j < len; j++) {
      if (map[s1[j] - 'a'] > map[s2[j] - 'a']) {
        return 0;
      }
      if (map[s1[j] - 'a'] < map[s2[j] - 'a']) {
        isEqual = 0;
        break;
      }
    }
    if (isEqual && n > m) {
      return 0;
    }
  }
  return 1;
}