传送门
解题思路：
-
先用 hash 记录 order 的字典顺序；
-
再两两比较 words 数组里面的字符串是不是满足字典序；
复杂度：
-
时间复杂度：O(m*n)，其中 m 为字符串数组的长度，n 为数组中字符串的平均长度，每个字符串需要前一个字符串进行比较，因此时间复杂度为 O(m*n)；
-
空间复杂度：O©，其中 C 表示字母表的长度，需要存储字母表 order 每个字符的字典序索引，题目中给定的字母表的长度为 C = 26；
代码实现：
var isAlienSorted = function (words, order) {
let map = {}
const len = order.length
for (let i = 0; i < len; i++) {
map[order[i]] = i
}
function isAfterWordBigger(w1, w2) {
const len1 = w1.length
const len2 = w2.length
for (let i = 0; i < len1 && i < len2; i++) {
if (map[w1[i]] < map[w2[i]]) {
return true
} else if (map[w1[i]] > map[w2[i]]) {
return false
}
}
// 遍历退出后，前面字符的字典序完全相同，不分胜负，则更长的一方字典序更大
return len2 >= len1 ? true : false
}
// 两两判断 words 数组里面的元素，是不是按字典序排列的
for (let i = 0; i < words.length - 1; i++) {
if (!isAfterWordBigger(words[i], words[i + 1])) {
return false
}
}
return true
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
709.转换成小写字母
上一篇
评论
