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

这篇具有很好参考价值的文章主要介绍了⭐北邮复试刷题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;
    }
}

结果：

⭐北邮复试刷题LCR 034. 验证外星语词典__哈希思想 (力扣119经典题变种挑战),Leetcode每日刷题,# 哈希思想与哈希映射,哈希算法,leetcode,散列表,北邮,Java 文章来源地址https://www.toymoban.com/news/detail-836093.html