⭐北邮复试刷题LCR 034. 验证外星语词典__哈希思想 (力扣119经典题变种挑战)

LCR 034. 验证外星语词典

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

题解：

本题我们还是以数组形式常规创建hash映射，区别为hash数组元素对应的值我们选用字母在所给order字符串中的顺序，以此作为优先级；
因此在比较两字符串时，我们转码为数字形式，进行优先级比对即可；

代码：

class Solution {public boolean isAlienSorted(String[] words, String order) {int hash[] = new int[26];for(int i=0;i<order.length();i++){char tmp = order.charAt(i);hash[tmp - 'a'] = i+1;}if(words.length == 1)return true;for(int i=1;i<words.length;i++){String left = words[i-1];String right = words[i];// 利用哈希数组将字符转码为数字，利用数字比较// 因数字较大超过10，不可直接利用十进制数大小直接比较boolean flag = charToNum(left,right,hash);// flag为每次比较的结果，而我们要的是总的比较结果if(!flag){return false;}}return true;}public boolean charToNum(String l ,String r ,int[] hash){int llen = l.length();int rlen = r.length();int lnum[] = new int[llen];int rnum[] = new int[rlen];for(int i=0;i<llen;i++){lnum[i] = hash[l.charAt(i) - 'a'];}for(int i=0;i<rlen;i++){rnum[i] = hash[r.charAt(i) - 'a'];}for(int i=0;i<llen && i<rlen;i++){// 注意审题，是只要两个单词之间出现大于的字符即算成功，而不是要求两个单词之间每对都为大于关系if(lnum[i] < rnum[i])return true;else if(lnum[i] > rnum[i])return false;}if(llen == rlen || llen < rlen)return true;return false;}
}

结果：