LeetCode LCR 114. 火星词典
题目描述
题意分析
单词已经按未知字母顺序排好，要求返回输入中出现过的全部字符的一种合法顺序。多个答案时任意一个即可；若单词次序无法由任何字母顺序解释，返回空字符串。
解法：相邻词首个差异建图与拓扑排序
核心思路
[!blue]
字典序由两个单词的第一处不同字符决定。比较相邻单词
w1、w2，找到首个差异位置j后，只能推出w1[j]排在w2[j]之前，建立这一条有向边；后续字符不再提供顺序约束。若较短单词耗尽仍没有差异，两者相同或互为前缀。前词更长时，它排在了自己的严格前缀之前，无论怎么安排字母都不合法，应立即返回空字符串；其他情况不需要加边。检查相邻单词已经足够，因为它们全部满足顺序后，整个列表也按字典序有序。
先注册所有出现过的字符，再建约束图，才能保留没有边的孤立字符。代码用集合保存后继，同一条边只存一次，因此也只能在成功加入新边时增加目标字符的入度，保证增加与后续删除的次数对应。
建图后进行拓扑排序。
indegree[ch]为尚未输出的前驱数量，所有零入度字符入队；每次输出一个字符，就将其后继入度减一，减到 0 时加入队列。每个被输出的字符都排在所有前驱之后，因此所得顺序满足全部相邻单词约束。最后必须检查输出长度是否等于已出现的字符数。若不足，剩余图中存在环，字符先后关系相互矛盾；若相等就返回结果。前缀矛盾不一定产生任何边，必须在建图时单独检查，不能只依靠拓扑判环。
解题步骤
- 遍历所有字符，初始化邻接集合和入度表。
- 逐对比较相邻单词，定位第一处不同字符。
- 没有差异且前词更长时返回空串；有差异时加入对应有向边，仅对新边增加入度。
- 将全部零入度字符入队，依次输出，并沿出边解除后继约束。
- 输出覆盖全部已知字符时返回答案，否则返回空串。
代码实现
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为不同字符数，E为去重后的边数。每个单词最多参与前后两次相邻比较；拓扑排序各处理一次节点和边。- 空间复杂度：$O(V+E)$，保存约束图、入度和队列。字符集只有 26 个小写字母，图的规模有固定上限。
关键点总结
[!green]
- 只从相邻单词的首个差异提取顺序，不能继续比较后面的字符来加边。
- 长词在其严格前缀之前与约束成环是两种不同的无解原因。
- 所有出现过的字符都要输出，包括不参与任何边的字符。
- 邻接集合已经去重时，入度也必须只计算不同的边；多个零入度字符可任选一个先输出。
易错点总结
[!yellow]
- 先注册全部出现的字符，孤立字符也应进入答案。
- 相邻单词只由第一处不同字符产生一条约束；长词排在其严格前缀之前时直接无解。
- 邻接集合去重时，入度也只对新边加一；最后检查输出覆盖全部字符。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 953. 验证外星语词典 | 简单 | 原题给定字母顺序后验证词典，本题从相邻单词的第一个不同字符反推先后约束。 |
| 210. 课程表 II | 中等 | 推导字母边之后，复用拓扑排序输出一个符合依赖关系的顺序。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！