一 目录
不折腾的前端，和咸鱼有什么区别
| 目录 |
|---|
| 一 目录 |
| 二 前言 |
| 三 解题及测试 |
| 四 LeetCode Submit |
| 五 解题思路 |
二 前言
难度：简单
涉及知识：哈希表
题目地址：https://leetcode-cn.com/problems/verifying-an-alien-dictionary/
题目内容：
某种外星语也使用英文小写字母，
但可能顺序 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 中的所有字符都是英文小写字母。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/verifying-an-alien-dictionary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
三 解题及测试
小伙伴可以先自己在本地尝试解题，再回来看看 jsliang 的解题思路。
LeetCode 给定函数体：
/**
* @param {string[]} words
* @param {string} order
* @return {boolean}
*/
var isAlienSorted = function(words, order) {
};
根据上面的已知函数，尝试破解本题吧~
确定了自己的答案再看下面代码哈~
index.js
/**
* @name 验证外星语词典
* @param {string[]} words
* @param {string} order
* @return {boolean}
*/
const isAlienSorted = (words, order) => {
order = ' ' + order; // 我们将空字符串定义为空白字符，权重为 0
for (let i = 0; i < words.length - 1; i++) {
const length = Math.max(words[i].length, words[i + 1].length);
for (let j = 0; j < length; j++) {
const prevIndex = order.indexOf(words[i][j] || ' ');
const nextIndex = order.indexOf(words[i + 1][j] || ' ');
if (prevIndex > nextIndex) {
return false;
} else if (prevIndex < nextIndex) {
break;
} else {
continue;
}
}
}
return true;
};
console.log(isAlienSorted(['hello', 'leetcode'], 'hlabcdefgijkmnopqrstuvwxyz')); // true
console.log(isAlienSorted(['word', 'world', 'row'], 'worldabcefghijkmnpqstuvxyz')); // false
console.log(isAlienSorted(['apple', 'app'], 'abcdefghijklmnopqrstuvwxyz')); // false
node index.js 返回：
true
false
false
四 LeetCode Submit
Accepted
* 115/115 cases passed (72 ms)
* Your runtime beats 51.85 % of javascript submissions
* Your memory usage beats 80 % of javascript submissions (34 MB)
五 解题思路
很高兴我开始研究外星语了，啥时候让我接触下外星人~
LeetCode 强大的题目内容
那么，咱们按惯例，还是先转译下题目。
LeetCode 题目都要转译，它是不是外星XXX……
分析如下：
已知有一串字符
words：['word', 'world', 'row']。然后有一个字母顺序表
order：worldabcefghijkmnpqstuvxyz。这些单词
words需要按照order的顺序进行排序，例如words中有单词['word', 'world', 'row']，那么先比较第一个字母，即w, w, r，这时候r在w后面无异议；接着比较第二个字母，即o, o（此时第三个单词row已经排除了）……以此类推，直至所有单词比较完毕，无意义则返回
true，否则返回false。
那么直接上代码：
暴力破解
const isAlienSorted = (words, order) => {
order = ' ' + order; // 我们将空字符串定义为空白字符，权重为 0
for (let i = 0; i < words.length - 1; i++) {
const length = Math.max(words[i].length, words[i + 1].length);
for (let j = 0; j < length; j++) {
const prevIndex = order.indexOf(words[i][j] || ' ');
const nextIndex = order.indexOf(words[i + 1][j] || ' ');
if (prevIndex > nextIndex) {
return false;
} else if (prevIndex < nextIndex) {
break;
} else {
continue;
}
}
}
return true;
};
思路就如 jsliang 所分析的那样：
首先重定义
order，因为根据案例 3 所说，需要对字符串进行补充，例如app和apple比较的时候，应该是app和apple比较（注意app后面加了 2 个空格）。然后通过
for遍历words，因为我们使用双指针，所有应该设置条件是i < words.length - 1。接着我们通过
Math.max获取两者的最大长度，避免app和apple比较失败的情况。再来就是遍历
words[i]和words[i + 1]这两者，我们以order为哈希表，进行索引的查找。最后就是比较每个单词的索引，如果前者大于后者（
prevIndex > nextIndex），那么说明这个是不符合规定的；如果前者小于后者，那么这个单词是 OK 的，我们应该中止这次循环，直接进入到words[i + 1]和words[i + 2]的比较；如果这两个单词是相同的，那么就进入下一个字符的比较~
这样，我们就完成了外星语词典的验证，Submit 提交为：
Accepted
* 115/115 cases passed (72 ms)
* Your runtime beats 51.85 % of javascript submissions
* Your memory usage beats 80 % of javascript submissions (34 MB)
好了，我知道外星语用法了，赶紧告诉我去哪里找外星人~
如果小伙伴们有更好的思路想法，欢迎评论留言或者私聊 jsliang~
不折腾的前端，和咸鱼有什么区别！
jsliang 会每天更新一道 LeetCode 题解，从而帮助小伙伴们夯实原生 JS 基础，了解与学习算法与数据结构。
浪子神剑 会每天更新面试题，以面试题为驱动来带动大家学习，坚持每天学习与思考，每天进步一点！
扫描上方二维码，关注 jsliang 的公众号（左）和 浪子神剑 的公众号（右），让我们一起折腾！
jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。