LeetCode LCR 034. 验证外星语词典
题目描述
题意分析
给定外星语的字母顺序
order，判断单词列表是否已经按这套字典序非递减排列。相邻两个单词允许相同，任务是验证原顺序，不需要重新排序。字典序仍由第一个不同字符决定，只是字符大小改用
order中的名次。若公共部分完全相同，短词排在长词前面，因此长词不能出现在自身严格前缀之前。
解法：自定义字母排名比较
核心思路
[!blue]
先建立“字符 → 在
order中的名次”映射，名次越小表示越靠前。比较时拿到字符就能直接查询它的排名，无需反复扫描整个order。只需检查每一对相邻单词。字典序具有传递性，相邻各对都满足前者不大于后者，整个列表就有序；遇到一对逆序即可返回
false。比较单词时，从左到右跳过相同字符。第一处名次不同若前者更大，则这一对逆序；若前者更小，这一对已经合法，必须立即结束比较，后续字符不能推翻这个结论。
Java 把已经用完的单词对应名次记为
-1，并扫描到较长单词的长度。真实名次都不小于0，所以短词会在结束的位置自然判为更小，统一处理前缀关系。Go 只扫描公共长度，用flag记录是否始终相同；只有尚未分出大小时，才检查前词是否更长。
解题步骤
- 遍历
order，记录每个字母的名次；映射方向必须是由字母查询排名。- 依次检查
words[i]与words[i + 1]，从首字符开始比较自定义名次。- 名次相等则继续，前词名次更大则返回
false，更小则结束当前对的比较。- 若公共部分始终一致，按长度判断：较短者可以在前，较长者不能在前。Java 用
-1哨兵隐式完成，Go 用长度判断显式完成。- 所有相邻对通过后返回
true，只有一个单词时也会自然通过。
代码实现
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();
int 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个字母，每个单词最多参加左右两次相邻比较。- 空间复杂度：$O(1)$，Java 数组和 Go 映射都只记录固定
26种字母的名次。
关键点总结
[!green]
- 名次表只改变字符的比较规则，不改变字典序由首个差异决定的原则。
- 相邻比较利用传递性完成全局验证，无需排序或比较所有单词对。
- 前缀关系必须处理，但只能在公共部分完全相同时由长度决定。
易错点总结
[!yellow]
- 建表方向是字母到名次，不能直接按字母原有编码大小比较。
- 一旦前词在首个不同位置更小，就结束这一对；继续比较可能错误地把合法顺序判反。
- 不能遗漏长词在短前缀之前的情形，也不能在字符已经分出大小后再强行比较长度。
- 完全相同的两个词允许相邻，不能将非递减要求写成严格递增。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 269. 火星词典 | 困难 | 本题已知字母序并验证单词排列，原题反过来从单词排列推导字母偏序。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！