LeetCode 953. 验证外星语词典

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 腾讯
标签
数组 字符串 哈希表

题目描述

✅ 953. 验证外星语词典

image-20260929105341436

image-20260929105341615

题意分析

给定 26 个小写字母在外星语言中的先后顺序，判断原单词数组是否按这套字典序非递减排列。单词可以相同；比较规则仍由第一个不同字符决定，前缀相同时短词在前。

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

核心思路

[!blue]

字符原本的编码大小不能代表新字母表的顺序。先建立 rank[c - 'a']，记录字母 c 在 order 中的位置；之后比较两个字符，就比较它们的名次。

字典序具有传递性，只需检查每对相邻单词：如果前一个都不大于后一个，整个数组就有序；任何一对逆序都足以判定失败。

比较 w1、w2 时，从首字符开始扫描共同长度。相同就继续；首次出现不同字符时，若前词字符名次更大，立即返回 false；若更小，这一对已经有序，应停止本对比较，继续检查后面的单词对。后续字符和词长都不能推翻首个不同字符的结论。

只有共同部分完全相同时，才由长度决定大小：前词比后词长，说明后词是前词的严格前缀，顺序错误；否则这一对合法。代码用 decided 区分“已由不同字符确定前词更小”和“共同部分全相同”，防止在前一种情况下错误地再按长度否定。

解题步骤

  1. 扫描 order，把每个字母映射为它的名次。
  2. 依次取相邻两个单词，令 decided = false。
  3. 从头比较共同长度内的名次。前词字符更大就返回 false；更小就令 decided = true 并停止本对扫描。
  4. 若没有分出大小，检查前词是否更长，是则返回 false。
  5. 所有相邻单词都通过后返回 true。只有一个单词或相邻两词完全相同，都不会构成逆序。

代码实现

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());
            // 已在共同可比较的部分遇到首个不同字符，并确定前词更小。
            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 := 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+26)$，L 为全部单词总长度，每词至多参与相邻两次比较。
  • 空间复杂度：$O(26)$，名次表。

关键点总结

[!green]

  • 映射是“字母到名次”，使每次字符比较都符合给定字母表。
  • 相邻单词逐对有序，通过传递性保证整个数组有序。
  • 首个不同字符优先；只有共同部分全相同时才比较长度。

易错点总结

[!yellow]

  • 直接比较字符编码，会忽略外星字母表的顺序。
  • 首个不同字符已经确定前词更小后仍继续比较，可能被后面的字符误导。
  • 一对单词合法时只能结束这一对的检查，不能直接返回整个数组有序。
  • 忘记前缀长度判断，会接受长词排在其严格前缀之前的情况。
  • 完全相同的单词符合非递减要求，长度相等不能判为失败。

相似题目

题目 难度 关联与区别
269. 火星词典 困难 本题已知字母序并验证单词排列，原题反过来从单词排列推导字母偏序。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/28180413
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！