LeetCode 953. 验证外星语词典

Categories:

题目描述
思路分析
1. 解法一：哈希表映射 + 逐对比较（推荐）
相似题目

题目描述

✅ 953. 验证外星语词典

思路分析

解法一：哈希表映射 + 逐对比较（推荐）

核心思路：

将外星字母表 order 中每个字符的顺序存入哈希表（rank 数组），实现 O(1) 查询

对相邻的两个单词逐字符比较：若某字符在外星字典中排名更小则合法；若更大则非法；若某前缀相同但前一个单词更长则非法

遍历所有相邻对，全部合法才返回 true

复杂度分析：

时间复杂度：O(m × n)，其中 m 表示单词数量，n 表示单词的平均长度

空间复杂度：O(1)，rank 数组长度固定为 26

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        // 构建字符到顺序的映射
        int[] rank = new int[26];
        for (int i = 0; i < order.length(); i++) {
            rank[order.charAt(i) - 'a'] = i;
        }

        // 逐对比较相邻单词
        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i];
            String w2 = words[i + 1];
            int minLen = Math.min(w1.length(), w2.length());
            boolean foundDiff = false;

            for (int j = 0; j < minLen; j++) {
                int r1 = rank[w1.charAt(j) - 'a'];
                int r2 = rank[w2.charAt(j) - 'a'];

                if (r1 < r2) {
                    // 当前对合法，跳出字符比较
                    foundDiff = true;
                    break;
                } else if (r1 > r2) {
                    // 当前对非法
                    return false;
                }
            }

            // 前缀相同，但 w1 更长则非法
            if (!foundDiff && w1.length() > w2.length()) {
                return false;
            }
        }

        return true;
    }
}

func isAlienSorted(words []string, order string) bool {
    // 构建字符到顺序的映射
    rank := [26]int{}
    for i, ch := range order {
        rank[ch-'a'] = i
    }

    // 逐对比较相邻单词
    for i := 0; i < len(words)-1; i++ {
        w1, w2 := words[i], words[i+1]
        minLen := len(w1)
        if len(w2) < minLen {
            minLen = len(w2)
        }
        foundDiff := false

        for j := 0; j < minLen; j++ {
            r1 := rank[w1[j]-'a']
            r2 := rank[w2[j]-'a']

            if r1 < r2 {
                // 当前对合法，跳出字符比较
                foundDiff = true
                break
            } else if r1 > r2 {
                // 当前对非法
                return false
            }
        }

        // 前缀相同，但 w1 更长则非法
        if !foundDiff && len(w1) > len(w2) {
            return false
        }
    }

    return true
}

相似题目

题目	难度	考察点
242. 有效的字母异位词	简单	哈希表、字符串
791. 自定义字符串排序	中等	哈希表、排序
1002. 查找共用字符	简单	哈希表、字符串
49. 字母异位词分组	中等	哈希表、排序
1636. 按照频率将数组升序排序	简单	哈希表、排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/28180413