LeetCode 953. 验证外星语词典

2024-12-17 HGNULB 约 10 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 953. 验证外星语词典

题意分析

外星语同样使用 26 个小写字母，但字母表顺序被打乱了，order 就是这门语言的字母表（26 个字母的一个排列）。给一组单词 words，判断它们是不是按照这门语言的字典序非递减排列的。

题面里有两个必须精确落实的定义。第一，字典序的定义：比较两个单词时，从左往右找第一个不同的字符，谁的字符在字母表里靠前谁就小；如果一直到较短单词结束都没有不同字符，那么短的那个更小。第二，「已排序」的判定对象是相邻对——只要每一对相邻单词都满足前者不大于后者，整体就有序，这来自字典序的传递性。

约束里 order 恰好是 26 个字母的全排列，单词全是小写字母，单词数与单词长度都不大（百级）。「26 个字母」这个数字是最强的信号：它意味着字母到序号的映射可以用一个长度 26 的定长数组完成，查询 $O(1)$，根本不需要哈希表。规模小也说明本题考的是定义落实的准确性，不是效率。

边界要盯住三处。其一，前缀关系：["apple", "app"] 中 app 是 apple 的前缀且更短，所以 apple 排在前面是非法的，这是本题最高频的漏判。其二，两个单词完全相同：非递减允许相等，必须返回合法。其三，words 只有一个单词时不存在相邻对，直接合法——好的实现应让它自然落入主循环（i < n - 1 一次都不执行）。

还有一点：题目要的是「是否已排序」，不是要求我们去排序。所以不需要真的排序再比对，只需逐对验证，这也是为什么线性扫描就够。

解法：rank 映射 + 相邻单词比较

核心思路

最朴素的做法是：写一个按外星序比较两个单词的比较器，把 words 复制一份排序，再看排序结果与原数组是否一致。这能得到正确答案，但代价是 $O(L \cdot n \log n)$ 的时间与 $O(n)$ 的额外空间，而且完全是多余的——判断「是否有序」不需要知道「有序时长什么样」。

瓶颈在于把「验证」误当成了「构造」。观察：字典序是一个全序关系，具有传递性，所以 w[0] <= w[1] <= ... <= w[n-1] 等价于所有相邻对都满足 w[i] <= w[i+1]。只要逐对验证，一次线性扫描即可，不必排序。

第二个观察是关于字符比较的。外星序里字母的大小不再是字符本身的大小，但只要预处理出 rank[c] = c 在 order 中的下标，比较 a 与 b 就等价于比较 rank[a] 与 rank[b]。因为 order 是 26 个字母的排列，rank 是一个双射，比较关系被完整保留。这一步把「自定义序」彻底归约成了「整数比较」，后续逻辑就和普通字典序完全一样了。

于是单对比较的规则可以精确写成：设两词公共长度为 minLen，从左往右扫描，

若在某位 j 有 rank[w1[j]] < rank[w2[j]]，则 w1 < w2，这一对已经判定合法，后面的字符完全不用看；

若有 rank[w1[j]] > rank[w2[j]]，则 w1 > w2，整体立刻不合法，直接返回 false；

若扫完 minLen 位都相等，说明较短者是较长者的前缀（或两词相同），此时合法当且仅当 len(w1) <= len(w2)。

代码里用一个布尔量 decided 记录「是否在公共前缀内就分出了胜负」，它维持的不变量是：内层循环退出时，decided 为真当且仅当存在某位使 w1 严格小于 w2。只有 decided 为假时，才需要拿长度做最后裁决。这个变量正是前缀情况不被漏掉的关键。

解题步骤

构建 rank[26]：遍历 order，令 rank[order[i] - 'a'] = i。为什么用定长数组而不是哈希表：字符集固定为 26 个小写字母，数组下标就是天然的完美哈希，查询 $O(1)$ 且没有装箱与哈希计算开销。注意映射方向是「字母 → 名次」，反过来写成 rank[i] = order[i] - 'a' 得到的是「名次 → 字母」，用它比较会得到毫无意义的结果。

外层枚举相邻对 i 从 0 到 n - 2，取 w1 = words[i]、w2 = words[i+1]。为什么只比相邻对：字典序有传递性，相邻全部有序即可推出整体有序，比较 $O(n)$ 对而非 $O(n^2)$ 对。

准备 minLen 与 decided：minLen 是两词长度较小者，超出它就没有可比的字符了；decided 初始为 false，语义是「是否已在公共前缀内分出大小」。

内层逐位比较：取出 r1 = rank[w1[j]]、r2 = rank[w2[j]]。r1 < r2 时置 decided = true 并 break——这一对已判定合法，继续比下去毫无意义且可能误判（后面的位本来就允许任意）。r1 > r2 时直接 return false——整个数组已经不可能有序，无需再看其余对。两者都不成立说明这一位相等，继续下一位。

前缀裁决：内层结束后若 decided 仍为 false，说明公共部分完全相同，此时若 len(w1) > len(w2) 返回 false。为什么用 > 而不是 >=：长度相等意味着两词完全相同，非递减允许相等，必须放行。

全部通过返回 true：外层跑完说明每一对都合法。

以 words = ["word", "world", "row"]、order = "worldabcefghijkmnpqstuvxyz" 走一遍。先建 rank：w=0、o=1、r=2、l=3、d=4，其余依次往后。
第一对 word 与 world，minLen = 4。j=0：w 与 w，rank 都是 0，相等，继续。j=1：o 与 o，相等。j=2：r 与 r，相等。j=3：d 与 l，rank[d] = 4、rank[l] = 3，4 > 3 成立，说明 word > world，立刻返回 false。
与预期一致——在这门外星语里 l 排在 d 前面，所以 world 应该排在 word 之前。

再看一个走完全程的用例 words = ["app", "apple"]、order 为正常字母表。minLen = 3，三位全相等，内层跑完 decided 仍为 false；长度 3 > 5 不成立，这一对合法；外层结束返回 true。若把两词调换成 ["apple", "app"]，同样三位相等、decided 为 false，但 5 > 3 成立，返回 false——前缀规则正是靠这一步生效的。

代码实现

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        // rank[字母] = 该字母在外星字母表中的名次。
        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());
            // decided 表示是否在公共前缀内就分出了「严格小于」。
            boolean decided = 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) {
                    decided = true;
                    break;
                }
                if (r1 > r2) {
                    return false;
                }
            }

            // 公共部分全等时，短的必须排在前面。
            if (!decided && w1.length() > w2.length()) {
                return false;
            }
        }

        return true;
    }
}

func isAlienSorted(words []string, order string) bool {
    // rank[字母] = 该字母在外星字母表中的名次。
    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)
        }
        // decided 表示是否在公共前缀内就分出了「严格小于」。
        decided := false

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

            if r1 < r2 {
                decided = true
                break
            }
            if r1 > r2 {
                return false
            }
        }

        // 公共部分全等时，短的必须排在前面。
        if !decided && len(w1) > len(w2) {
            return false
        }
    }

    return true
}

复杂度分析

时间复杂度：$O(L)$，其中 L 为所有单词的总字符数。凭什么：预处理 rank 是固定的 26 次操作；每一对相邻单词最多比较 minLen 个字符，而 words[i] 至多参与两次比较（作为前者一次、作为后者一次），所以总比较字符数不超过 $2L$，每次比较是常数操作。

空间复杂度：$O(1)$。凭什么：只额外开了长度固定为 26 的 rank 数组和几个标量，与输入规模无关；没有复制单词也没有排序所需的辅助数组。

关键点总结

字符集固定为 26 个小写字母时，定长数组就是最好的哈希表：$O(1)$ 查询、无哈希开销、无装箱，凡是题面给出「小写字母」都应优先考虑它。

自定义序的题目统一套路是先建立「字符 → 名次」的映射，把自定义比较归约成整数比较，之后所有逻辑都可以照搬标准写法。

判断「是否有序」只需验证相邻对，这是全序关系传递性的直接推论；把「验证」误做成「排序后比对」是常见的复杂度浪费。

字典序比较必须显式处理「公共前缀相同」的分支，用一个布尔量标记「是否已分出胜负」比在循环外重新推断状态更不容易出错。

面试视角：这题的分水岭就是前缀用例。写完后主动举 ["apple","app"] 说明短词必须在前，再举 ["app","app"] 说明相等合法，面试官立刻能判断你是否真的理解字典序定义；若被追问进阶，可以提 269 题——那题是反过来由单词顺序推导字母表，需要拓扑排序。

提前 break 与提前 return 的区别要说清楚：break 只结束当前这一对的比较，return false 结束整个判定，写混会让已判定合法的对继续被比较从而误判。

易错点总结

错误写法：漏掉前缀裁决那一行 → 用例 words = ["apple","app"]、正常字母表中，公共三位全等后没有任何判断，函数返回 true，而正确答案是 false。

错误写法：前缀裁决写成 w1.length() >= w2.length() → 用例 ["app","app"] 中两词相同，长度相等被判非法返回 false，而非递减允许相等，正确答案是 true。

错误写法：r1 < r2 时只 break 而不置 decided = true → 用例 ["ab","ba"]（正常字母表）中第 0 位就分出 a < b 而跳出，随后长度相等虽不触发误判，但换成 ["abc","b"] 时 decided 为假且 3 > 1，被错误判为 false。

错误写法：r1 > r2 时写成 break 而不是 return false → 用例 ["world","word"] 中第 3 位判出前者更大却只跳出内层，外层继续检查下一对，最终返回 true，漏报逆序。

错误写法：rank 建反，写成 rank[i] = order.charAt(i) - 'a' → 用例 order = "worldabcefghijkmnpqstuvxyz"、words = ["word","world"] 中比较的是名次对应的字母而非字母对应的名次，结果随机正确或错误，逻辑不可解释。

错误写法：直接用字符本身比较 w1.charAt(j) > w2.charAt(j) → 用例 order = "hlabcdefgijk..."、words = ["hello","leetcode"] 中按正常序 h < l 判为合法，但外星序里 h 确实在 l 前面时侥幸正确，一旦换成 order 把 l 排在 h 前，答案就反了。

错误写法：外层循环写成 i < words.length 再访问 words[i+1] → 用例 ["a","b"] 在 i = 1 时越界，Java 抛数组越界异常，Go 直接 panic。

错误写法：内层比较到 w1.length() 而不是 minLen → 用例 ["apple","app"] 在 j = 3 时访问 w2.charAt(3) 越界崩溃，前缀情况必须靠长度而不是靠继续读字符来裁决。

错误写法：只比较首字符是否有序 → 用例 ["word","world"] 首字符都是 w 被判合法，实际第 3 位已逆序，答案应为 false。

错误写法：为了「稳妥」把所有单词两两比较 → 用例中答案虽对，但复杂度升到 $O(n^2 L)$，且面试官会追问为什么不用传递性，属于对定义理解不到位的信号。

错误写法：把 words 用外星比较器排序后与原数组比对是否相等 → 用例上正确，但多出 $O(n \log n)$ 时间与 $O(n)$ 空间，且需要额外写比较器，白白放大了出错面。

相似题目

题目	难度	考察点
LCR 034. 验证外星语词典	简单	与本题同题，可直接套用同一份实现
269. 火星词典	困难	方向反过来：由单词顺序反推字母表，需建图并拓扑排序，还要判环与非法前缀
791. 自定义字符串排序	中等	同样先建字符名次映射，但要真的重排字符串而不只是验证
14. 最长公共前缀	简单	逐位比较到最短长度为止，练的是公共前缀边界而不涉及自定义序
242. 有效的字母异位词	简单	同样用长度 26 的计数数组，但比的是字符频次而非顺序
944. 删列造序	简单	也按列逐字符判非递减，但判定对象是列且各列独立，答案是计数不是布尔
392. 判断子序列	简单	双指针跨长度扫描，考的是子序列匹配而不是字典序大小