LeetCode LCR 114. 火星词典
目录
题目描述
题意分析
给定一批由小写字母组成的单词，它们已经按照某种未知的字母表顺序排成了升序。要反推出这套字母表的一个合法顺序并返回；如果输入本身自相矛盾，返回空字符串；如果存在多个合法顺序，返回任意一个即可。
「已按新字典序升序排列」是全部信息的来源。字典序比较的规则决定了信息量非常有限：两个单词一旦在某个位置分出高下，后面的字符就完全不再参与比较。因此每一对相邻单词最多只能贡献一条「某字符排在某字符之前」的结论，多提取一条都是凭空捏造。
「返回任意一个」这句话说明答案通常不唯一，只要与所有已知约束相容即可，不需要追求字典序最小或其他附加性质。
非法输入有两种形态，必须分开处理。一种是环：约束互相矛盾，比如同时要求
a在b前、b又在a前。另一种是前缀矛盾：在真实的字典序里，短的前缀必须排在长的整词之前，所以形如["abc", "ab"]的输入不可能出现，这类矛盾在建图阶段就要识别出来。还有一个容易被漏掉的要求：答案必须覆盖输入里出现过的全部字符，包括那些从未参与任何约束的孤立字符；同时不能包含从未出现过的字符。
规模上单词数与单词长度都不大，字符集又被限死在 26 个以内，所以复杂度的重心在建图的正确性而不是效率。
解法：拓扑排序
核心思路
暴力思路是枚举 26 个字母的所有排列，逐个检查是否让输入保持升序。这在逻辑上无懈可击，但排列数是阶乘级，完全不可行。
瓶颈在于枚举把「字母之间的先后」当成一团整体去猜，而实际上这些先后关系是可以被逐条读出来的。
观察相邻两个单词
w1与w2：从左往右逐位比较，在第一个不同的位置j上，w1[j]必须排在w2[j]之前——这就是一条明确的有向约束。而位置j之后的所有字符不受任何限制，因为字典序在j处就已经分出胜负了。如果一直比到较短单词耗尽都没有分歧，那么两者是前缀关系，此时只有「短的在前」是合法的；若反过来是长的在前，输入自相矛盾。把每条约束当作一条有向边，字符当作顶点，问题就转化成：求这张有向图的一个拓扑序。按入度剥离即可——入度为 0 的字符表示当前没有任何字符必须排在它之前，可以安全地放进答案；放进去之后把它指向的字符的入度各减一，新变成 0 的继续入队。
这个过程维持的不变量是：队列中的每个字符，其所有前驱都已经被写入答案；因此按出队顺序拼接得到的一定是一个合法拓扑序。当队列耗尽时，若答案长度等于字符总数，说明每个字符都被成功安置；若短于字符总数，说明剩下的字符入度始终降不到 0，即它们构成了环，输入非法。
解题步骤
- 先遍历所有单词的所有字符，为每个出现过的字符建立空的邻接集合并把入度初始化为 0。这一步不能省：孤立字符不参与任何边，只有在这里注册过，它才会以入度 0 的身份进入队列并出现在答案里。
- 逐对比较相邻单词
w1与w2。取两者长度的较小值作为比较上限，避免访问越界。- 从左往右找第一个不同的位置
j。这是唯一携带顺序信息的位置，找到后立即停止，绝不能继续为后面的字符加边。- 若一直比到上限都没有分歧，且
w1比w2更长，说明长词排在了它的前缀之前，直接返回空字符串。这是与环无关的第二类非法输入，必须单独判断。- 若在
j处分出高下，尝试加入边w1[j] -> w2[j]。加边前要先检查这条边是否已经存在，只有新边才让目标字符的入度加一。用集合去重是因为同一条约束可能被多对单词重复提供，重复计数会让目标字符的入度永远降不到 0。- 把所有入度为 0 的字符放入队列，作为拓扑排序的起点。
- 不断弹出队首字符追加到答案，并把它指向的每个字符入度减一，减到 0 的立刻入队。追加顺序就是最终顺序，不能倒序拼接。
- 最后比较答案长度与字符总数。相等则返回答案，否则说明存在环，返回空字符串。这个比较必须做，光靠「队列提前空」是判断不出来的——图里可能既有能正常排出的字符，又有独立成环的字符。
以
words = ["wrt", "wrf", "er", "ett", "rftt"]走一遍：先注册出现过的五个字符w、r、t、f、e，入度全部置 0。接着逐对比较——"wrt"与"wrf"在下标 2 处首次不同，加边t -> f，f的入度变 1；"wrf"与"er"在下标 0 处不同，加边w -> e，e的入度变 1；"er"与"ett"在下标 1 处不同，加边r -> t，t的入度变 1；"ett"与"rftt"在下标 0 处不同，加边e -> r，r的入度变 1。此时入度分别是w = 0、e = 1、r = 1、t = 1、f = 1，只有w入度为 0，队列初始化为[w]。出队w，答案变成"w"，它指向e，e的入度降到 0 入队；出队e，答案"we"，它指向r，r降到 0 入队；出队r，答案"wer"，它指向t，t降到 0 入队；出队t，答案"wert"，它指向f，f降到 0 入队；出队f，答案"wertf"。队列空，答案长度 5 等于字符总数 5，返回"wertf"。
代码实现
class Solution {
// 如果前一个单词更长且完全包含后一个单词，输入顺序本身非法，必须返回空字符串。
public String alienOrder(String[] words) {
Map<Character, Set<Character>> graph = new HashMap<>();
Map<Character, Integer> indegree = new HashMap<>();
for (String word : words) {
for (char ch : word.toCharArray()) {
graph.putIfAbsent(ch, new HashSet<>());
indegree.putIfAbsent(ch, 0);
}
}
for (int i = 0; i < words.length - 1; i++) {
String w1 = words[i];
String w2 = words[i + 1];
int len = Math.min(w1.length(), w2.length());
int j = 0;
while (j < len && w1.charAt(j) == w2.charAt(j)) {
j++;
}
if (j == len && w1.length() > w2.length()) {
return "";
}
if (j < len) {
char from = w1.charAt(j);
char to = w2.charAt(j);
if (graph.get(from).add(to)) {
indegree.put(to, indegree.get(to) + 1);
}
}
}
Queue<Character> queue = new ArrayDeque<>();
for (char ch : indegree.keySet()) {
if (indegree.get(ch) == 0) {
queue.offer(ch);
}
}
StringBuilder sb = new StringBuilder();
while (!queue.isEmpty()) {
char cur = queue.poll();
sb.append(cur);
for (char next : graph.get(cur)) {
indegree.put(next, indegree.get(next) - 1);
if (indegree.get(next) == 0) {
queue.offer(next);
}
}
}
if (sb.length() != indegree.size()) {
return "";
}
return sb.toString();
}
}
func alienOrder(words []string) string {
// 如果前一个单词更长且完全包含后一个单词，输入顺序本身非法，必须返回空字符串。
graph := make(map[byte]map[byte]struct{})
indegree := make(map[byte]int)
for _, w := range words {
for i := 0; i < len(w); i++ {
ch := w[i]
if _, ok := graph[ch]; !ok {
graph[ch] = make(map[byte]struct{})
}
if _, ok := indegree[ch]; !ok {
indegree[ch] = 0
}
}
}
for i := 0; i < len(words)-1; i++ {
w1 := words[i]
w2 := words[i+1]
minLen := len(w1)
if len(w2) < minLen {
minLen = len(w2)
}
j := 0
for j < minLen && w1[j] == w2[j] {
j++
}
if j == minLen && len(w1) > len(w2) {
return ""
}
if j < minLen {
from := w1[j]
to := w2[j]
if _, ok := graph[from][to]; !ok {
graph[from][to] = struct{}{}
indegree[to]++
}
}
}
queue := make([]byte, 0)
for ch, deg := range indegree {
if deg == 0 {
queue = append(queue, ch)
}
}
order := make([]byte, 0, len(indegree))
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
order = append(order, cur)
for next := range graph[cur] {
indegree[next]--
if indegree[next] == 0 {
queue = append(queue, next)
}
}
}
if len(order) != len(indegree) {
return ""
}
return string(order)
}
复杂度分析
- 时间复杂度：$O(C + V + E)$，其中 $C$ 是所有单词的字符总数（注册字符与逐对比较各扫一遍），$V$ 是出现过的不同字符数、不超过 26，$E$ 是去重后的边数、不超过 $26 \times 25$。因此实际运行时间由 $C$ 主导。
- 空间复杂度：$O(V + E)$，邻接集合、入度表、队列与答案缓冲的规模都被字符集大小封顶，在本题条件下相当于常数级。
关键点总结
- 字典序比较的信息量全部集中在「第一个不同的字符」上，之后的位置不提供任何顺序信息。多加一条边就是凭空引入约束，会把本来有解的输入判成有环。
- 前缀矛盾是与环并列的第二类非法输入，且只能在建图阶段发现。拓扑排序本身对它毫无察觉，漏掉这个判断的代码在有环用例上能过、在前缀用例上必挂。
- 所有出现过的字符都必须先注册进图和入度表。只从边里收集顶点，会让孤立字符从答案中凭空消失。
- 边要去重。同一条约束可能被多对单词重复提供，不去重就会把目标字符的入度加多次，而减的时候只减一次，导致它永远出不了队，程序误判为有环。
- 判定成功的标准是「答案长度等于字符总数」，而不是「队列自然耗尽」。图中可以同时存在能正常排出的部分和独立成环的部分，只看队列会漏判。
- 面试视角：这题的分值分布大致是建图四成、非法判定三成、拓扑三成。很多人一上来就默写拓扑模板，反而在建图和边界上丢分。更稳的开场是先把两类非法输入讲清楚，再谈图怎么建，最后才是模板。
- 面试视角：常见追问是「答案不唯一时怎么办」和「怎么判断答案是否唯一」。前者答任意拓扑序皆可；后者指出只要队列中某一时刻同时存在两个及以上的字符，顺序就不唯一——这正好是 444 题的考点，能顺势带出来会很加分。
易错点总结
- 错误写法：只从边里收集顶点，不预先注册所有出现过的字符。用例
["z", "z"]→ 两个单词相同不产生任何边，图为空，返回""，正确答案是"z"。- 错误写法：省略前缀矛盾的判断。用例
["abc", "ab"]→ 两词没有第一个不同字符，程序直接跳过这一对，最终输出某个字母顺序，而这个输入本身非法，正确答案是""。- 错误写法：找到第一个不同字符后继续为后面的位置加边。用例
["ab", "ba"]→ 除了真实约束a -> b，还捏造出b -> a，两条边成环，返回""，正确答案是"ab"。- 错误写法：加边时不做去重，直接给目标字符的入度加一。用例
["ab", "ac", "xb", "xc"]→ 约束b -> c被第一对和第三对各提供一次，c的入度被加到 2，而b出队时只减一次，c永远无法入队，返回""，而"abcx"是合法答案。- 错误写法：只要队列耗尽就直接返回已拼接的结果，不比较长度。用例
["zy", "xy", "zy"]→ 约束z -> x与x -> z成环，只有y能出队，返回"y"，正确答案是""。- 错误写法：比较上限取
w1的长度而不是两者较小值。用例["abc", "ab"]→ 比较到下标 2 时访问w2[2]，下标越界抛异常。- 错误写法：把出队字符倒序拼接成答案。用例
["wrt", "wrf", "er", "ett", "rftt"]→ 得到"ftrew"，正确答案是"wertf"；入度剥离的出队顺序本身就是正序。- 错误写法：认为答案必须覆盖全部 26 个字母，把未出现的字母也补进结果。用例
["z", "x"]→ 返回一个 26 字符的串，而题目只要求排出现过的字符，正确答案是"zx"。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 207. 课程表 | 中等 | 边直接给出，无需从数据中推导，只需回答是否有环 |
| 210. 课程表 II | 中等 | 在判环基础上输出一条完整拓扑序，是本题去掉建图难度后的骨架 |
| 310. 最小高度树 | 中等 | 无向树按度数为 1 从外向内剥离，判据与终止条件都与有向图不同 |
| 444. 序列重建 | 中等 | 重点从「是否有解」转向「解是否唯一」，需检查队列规模是否恒为 1 |
| 1462. 课程表 IV | 中等 | 要回答任意两点的可达性，需要在拓扑过程中维护传递闭包 |
| LCR 113. 课程表 II | 中等 | 与 210 同题，适合对比广度优先剥离与深度优先逆后序两种实现 |
| LCR 115. 序列重建 | 中等 | 与 444 同题，考察点集中在唯一性判定而非合法性判定 |
| 面试题 04.01. 节点间通路 | 中等 | 只判断两点是否连通，一次搜索即可，不涉及入度与顺序输出 |