LeetCode LCR 034. 验证外星语词典

Categories:

题目描述
思路分析
1. 解法一：字母顺序映射（推荐）
相似题目

题目描述

✅ LCR 034. 验证外星语词典

思路分析

解法一：字母顺序映射（推荐）

核心思路：

用数组记录外星字母顺序的排名 rank[c]。

逐对比较相邻单词，找到第一处不同字符即可判定顺序。

若所有字符都相同，长度更短者应排在前面，否则非法。

复杂度分析：

时间复杂度：O(total)，其中 total 表示所有单词字符总数。

空间复杂度：O(1)，仅使用常数级数组。

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++) {
            if (!inOrder(words[i], words[i + 1], rank)) {
                return false;
            }
        }

        return true;
    }

    private boolean inOrder(String a, String b, int[] rank) {
        int i = 0;
        int j = 0;
        while (i < a.length() && j < b.length()) {
            char ca = a.charAt(i);
            char cb = b.charAt(j);
            if (ca != cb) {
                return rank[ca - 'a'] < rank[cb - 'a'];
            }
            i++;
            j++;
        }
        return a.length() <= b.length();
    }
}

func isAlienSorted(words []string, order string) bool {
    rank := make([]int, 26)
    for i := 0; i < len(order); i++ {
        rank[order[i]-'a'] = i
    }

    for i := 0; i < len(words)-1; i++ {
        if !inOrder(words[i], words[i+1], rank) {
            return false
        }
    }

    return true
}

func inOrder(a, b string, rank []int) bool {
    i, j := 0, 0
    for i < len(a) && j < len(b) {
        ca := a[i]
        cb := b[j]
        if ca != cb {
            return rank[ca-'a'] < rank[cb-'a']
        }
        i++
        j++
    }
    return len(a) <= len(b)
}

相似题目

题目	难度	考察点
14. 最长公共前缀	简单	字符串比较
524. 通过删除字母匹配到字典里最长单词	中等	双指针
1138. 字母板上的路径	中等	字符映射
269. 火星词典	困难	拓扑排序
163. 缺失的区间	简单	顺序规则

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/41621489