| comments | difficulty | edit_url | tags | |||
|---|---|---|---|---|---|---|
true |
简单 |
|
某种外星语也使用英文小写字母，但可能顺序 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 <= 1001 <= words[i].length <= 20order.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 Trueclass 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;
}