LeetCode LCR 034. 验证外星语词典
目录
题目描述
题意分析
给一组单词
words和一个字符串order，order是 26 个小写字母的一个排列，代表外星语中字母的先后次序。判断words是否按这套次序升序排列（允许相等，即非递减）。「按某种次序排列」需要拆成两层。外层是相邻性：整体有序等价于每一对相邻单词都满足前者不大于后者，因为字典序比较具有传递性，不需要两两全比。这把 $O(n^2)$ 的比较量降到 $O(n)$ 对。
内层是单词比较规则。字典序的定义是：从左往右找第一个不同的字符，谁的字符靠前谁就小；若一路都相同，则短的那个更小（前缀关系）。这两条缺一不可，第二条是本题最常被忽略的地方——
"apple"与"app"的前三位完全相同，此时更短的"app"应当排在前面。唯一被改写的是「谁靠前」的判定依据：不再是字母表的天然顺序，而是
order给定的位置。所以需要一次预处理，把字符映射到它在order中的下标。约束里
order恰好是 26 个小写字母的排列，这保证了映射是双射、每个字符都有唯一下标，不存在缺失字符的情况。边界：只有一个单词时天然有序；相邻两词完全相同时合法；某个词是另一个的前缀时要按长度定序。
解法：哈希表统计状态
核心思路
直接的想法是写一个自定义比较器再调排序，看排完是否与原数组一致。这不但多了 $O(n \log n)$ 的排序开销，还要额外存一份数组，而我们其实只需要验证，不需要真的排序。
去掉排序之后，问题就是「逐对验证相邻单词」。于是第一件事是把「按
order比较字符」变成一次常数时间的操作。预处理的关键在于映射方向：要建的是「字符 → 它在
order中的位置」，而不是「位置 → 字符」。因为比较时手里拿着的是单词里的字符，需要立刻问出它排第几。所以写法是index[order.charAt(i) - 'a'] = i——下标是字符，值是名次。方向搞反会得到一个完全错误的比较依据。有了
index，比较两个单词就变成逐位比较它们字符的名次。这里定义一个统一的取值规则可以把「前缀」这条规则也吸收进来：下标越界时把名次取为-1。因为真实名次范围是[0, 25]，-1严格小于任何真实字符的名次，于是「短词已经耗尽而长词还有字符」自动等价于「短词在这一位更小」，正是前缀规则想要的结论。这样单词比较的逻辑就统一成一个循环：从第 0 位扫到两词长度的最大值，取出两边的名次
i1与i2。若i1 > i2，说明前一个词更大，整体无序，直接返回假；若i1 < i2，说明这一对已经分出胜负且顺序正确，立即跳出去看下一对；若相等则继续看下一位。循环的不变量是：进入第
j轮时，两词的前j位名次完全相同。正因为如此，第一次出现差异的那一位就唯一决定了两词的大小关系，比出结果后必须break而不能继续比——继续比会让后面的位错误地覆盖已经确定的结论。Go 版把这个逻辑拆成了另一种等价写法：先只比较公共前缀部分（循环到两词较短的长度），用一个标志位记录是否已经分出大小；若一路相同，则回到长度上判断——前一个词更长就说明违反前缀规则，返回假。两种写法的判定结果完全一致，前者靠
-1哨兵统一，后者靠显式的长度检查。
解题步骤
- 建名次表：
for (int i = 0; i < 26; ++i) index[order.charAt(i) - 'a'] = i;。下标是字符偏移、值是名次，方向不能反。order是 26 个字母的排列，所以循环恰好跑满 26 次且每个字符都被赋值一次。- 只比相邻对：
for (int i = 0; i < words.length - 1; ++i)，比较words[i]与words[i+1]。上界写length - 1是因为最后一个词没有后继；靠传递性，相邻全部合法即整体有序。- 逐位比较到较长的长度：
for (int j = 0; j < Math.max(l1, l2); ++j)。用最大值而不是最小值，配合越界取-1的规则，才能让前缀情形被这个循环覆盖到。- 取名次时处理越界：
i1 = j >= l1 ? -1 : index[w1.charAt(j) - 'a']，i2同理。-1小于所有真实名次，语义上正好是「这个词已经结束了，比任何字符都小」。- 三路判定：
i1 > i2返回假；i1 < i2跳出内层循环去看下一对；相等则继续。break是必须的，否则会用后面的位覆盖掉已经得出的正确结论。- 全部相邻对都通过则返回真。
以
words = ["word", "world", "row"]、order = "worldabcefghijkmnpqstuvxyz"走一遍。先建名次表：w是 0、o是 1、r是 2、l是 3、d是 4，其余字母从 5 开始依次排开。第一对
"word"与"world"：j=0两边都是w，名次都是 0，相等；j=1都是o，相等；j=2都是r，相等；j=3左边是d（名次 4）、右边是l（名次 3），4 > 3成立，立即返回假。这与题目预期一致——在这套字母序里l排在d前面，所以"world"应当排在"word"之前。再看一个返回真的用例
words = ["hello", "leetcode"]、order = "hlabcdefgijkmnopqrstuvwxyz"：h名次 0、l名次 1。第一对j=0时左边h名次 0、右边l名次 1，0 < 1成立，跳出内层循环；没有更多相邻对，返回真。注意后面的字符根本没被比较过——第一位已经定胜负，这正是break的价值。最后看前缀用例
words = ["apple", "app"]、order为正常字母序。j=0,1,2三位都是a、p、p，名次相等；j=3时左词还有字符l（名次 11），右词已越界取-1，11 > -1成立，返回假。这正是「长词不能排在它的前缀之前」这条规则，由-1哨兵自动实现，不需要单独写长度判断。
代码实现
class Solution {
public boolean isAlienSorted(String[] words, String order) {
// 建「字符 -> 名次」的映射，方向不能反。
int[] index = new int[26];
for (int i = 0; i < index.length; ++i) {
index[order.charAt(i) - 'a'] = i;
}
// 字典序有传递性，只需验证每一对相邻单词。
for (int i = 0; i < words.length - 1; ++i) {
String w1 = words[i];
String w2 = words[i + 1];
int l1 = w1.length(), l2 = w2.length();
// 扫到较长的长度，配合越界取 -1 覆盖前缀规则。
for (int j = 0; j < Math.max(l1, l2); ++j) {
int i1 = j >= l1 ? -1 : index[w1.charAt(j) - 'a'];
int i2 = j >= l2 ? -1 : index[w2.charAt(j) - 'a'];
if (i1 > i2) {
return false;
}
// 已分出大小，后面的位不能再参与判定。
if (i1 < i2) {
break;
}
}
}
return true;
}
}
func isAlienSorted(words []string, order string) bool {
// 建「字符 -> 名次」的映射，方向不能反。
index := make(map[byte]int)
for i := range order {
index[order[i]] = i
}
for i := 0; i < len(words)-1; i++ {
w1, w2 := words[i], words[i+1]
l1, l2 := len(w1), len(w2)
// flag 为真表示公共前缀一路相同，尚未分出大小。
flag := true
for j := 0; j < min(l1, l2) && flag; j++ {
i1, i2 := index[w1[j]], index[w2[j]]
if i1 > i2 {
return false
}
if i1 < i2 {
flag = false
}
}
// 公共前缀相同时，长的排在前面即违反前缀规则。
if flag && l1 > l2 {
return false
}
}
return true
}
复杂度分析
- 时间复杂度：$O(S)$，
S是所有单词的总字符数。建名次表是固定 26 次；每一对相邻单词最多比较到两者长度的最大值，每个单词至多参与两次比较（作为前者一次、作为后者一次），累计不超过 $2S$，每次比较都是常数时间的数组取值。- 空间复杂度：$O(1)$。名次表长度恒为 26，由字符集大小决定而与输入规模无关；除此之外只有若干整型变量，没有开与输入同阶的结构。Go 版用哈希映射存名次，同样是至多 26 项的常数空间。
关键点总结
- 「整体有序」等价于「相邻两两有序」，靠的是比较关系的传递性，这一步把验证从平方级降到线性，是所有「判断是否已排序」类题目的第一刀。
- 自定义字母序的题目，第一件事永远是建「字符 → 名次」的映射，把陌生的比较规则翻译成整数大小比较，后续逻辑就与普通字典序完全一致了。
- 用
-1当越界哨兵，把「前缀更小」这条规则并入统一的逐位比较，比写额外的长度分支更短也更不易漏；哨兵值必须严格小于所有合法值才成立。- 比出大小后必须立即跳出，字典序只由第一个不同的位置决定，继续比较会让结论被后续位覆盖。
- 前缀情形是字典序题目的高频陷阱，写完一定要用「长词在前、短词在后且互为前缀」的用例验一遍。
- 面试视角：面试官常追问「如果不是验证而是要求你按这套序排序呢」，答案是用同一个名次表写比较器再排序；再往上一层追问「如果
order未知，只给出有序的单词列表要你推出字母序呢」，那就是拓扑排序的题目，能顺着说出这条演进路线会显著加分。
易错点总结
- 映射方向写反：写成
index[i] = order.charAt(i) - 'a'，得到的是「名次 → 字符」，比较时取到的数值毫无意义，["hello","leetcode"]这类用例会随机地对或错。- 内层循环只扫到
min(l1, l2)且不补长度判断：["apple","app"]的公共前缀全部相同，循环结束后直接放行，错误返回真。- 比出大小后不
break：["hello","leetcode"]在第 0 位已确定顺序正确，若继续比较第 1 位的e与e、第 2 位的l与e，会因为l名次大于e而错误返回假。- 越界哨兵取
0而不是-1：0是order首字母的合法名次，["ab","a"]中短词越界后被当成首字母，与真实字符相等时会漏判。- 外层循环上界写成
words.length：访问words[i + 1]时越界，抛数组越界异常。- 直接用
w1.compareTo(w2)：比的是天然字母序，order = "hlabcdefgijkmnopqrstuvwxyz"下["hello","leetcode"]会被判成无序，自定义次序完全没被用上。- 认为相等的相邻单词非法：
["app","app"]是合法的非递减序列，若把i1 == i2且长度也相同的情形判成假，会错误返回。- 建名次表时循环次数用
order.length()之外的值：写成遍历 26 但order被误传成短串会越界；本题保证order恰好 26 位，但读题时要确认这一点再依赖它。- 用排序后比对原数组的方式实现：需要额外 $O(n)$ 空间和 $O(n \log n)$ 时间，且相等元素的稳定性会干扰判等，属于绕远路的写法。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 953. 验证外星语词典 | 简单 | 与本题同题，可直接套用名次表加相邻比较 |
| 269. 火星词典 | 困难 | 反过来做：由有序单词列表反推字母序，需要建图并做拓扑排序 |
| 791. 自定义字符串排序 | 中等 | 同样给定字符优先级，但要求真的重排字符串而不只是验证 |
| 165. 比较版本号 | 中等 | 同样是逐段比较、首个差异定胜负，但比较单位是数字且缺位要补零 |
| 944. 删列造序 | 简单 | 换成按列检查是否非递减，统计需要删除的列数而非整体判定 |
| 1122. 数组的相对排序 | 简单 | 同样先建「元素 → 优先级」的映射，再据此排序，未出现的元素另有规则 |
| 1061. 按字典序排列最小的等效字符串 | 中等 | 字符之间存在等价关系，需并查集归并后再取字典序最小的代表 |