LeetCode 269. 火星词典
题目描述
题意分析
一组单词已经按某种未知字母顺序排好，要求推导所有出现过的字母的一种合法排列。该排列只需让给定单词序列符合字典序，不要求恢复唯一顺序；如果约束矛盾，返回空字符串。
字典序由两个词的第一处不同字符决定；若一词是另一词的前缀，较短词必须在前。输出还要包含没有与其他字母形成直接约束的字符，每个出现过的字母输出一次。
解法：拓扑排序
核心思路
[!blue]
先把出现过的每个字符注册为图节点，再从相邻单词中提取字母的先后约束。比较相邻两词时，跳过共同前缀，若第一处不同字符分别是
a、b，前词排在后词之前就要求a在b之前，建立边a → b。这一处已经决定词序，后面不同的字符不再提供额外约束。如果较短长度以内完全相同，却是较长词排在前面，那么后词是前词的真前缀。无论怎样排列字母，都无法让这个顺序合法，应立即返回空字符串；完全相同的词，或较短前缀在前，则不增加边。
只比较相邻词就足够：若所有相邻词在推导出的字母序下都满足前后关系，整个单词列表也就有序，不必对所有词两两比较。同一条字母约束可能重复出现，邻接集合只新增一次边，入度也只能相应增加一次。
得到的是字母之间的部分先后关系，用拓扑排序补成完整排列。所有零入度字符都可以作为当前下一个输出，输出后删除它们的出边，释放后继。多个候选同时为零入度时任取一个，都符合题目允许返回任意合法顺序的要求。
若所有字符都被输出，每条边的起点一定在终点之前，词典约束全部满足。若队列耗尽仍有字符未输出，剩余依赖中存在环，无法排出完整字母序，必须返回空字符串，而不是已经输出的部分结果。
解题步骤
- 扫描全部单词，为每个出现字符建立邻接集合和初始零入度，保留孤立字符。
- 比较每对相邻词，找到首个不同字符；先排除长词在其短前缀之前的非法情况。
- 有首差时建立对应先后边，只有边首次出现才增加后继入度。
- 将全部零入度字符入队，依次输出并递减后继入度，新变为零的后继也入队。
- 输出数量等于出现过的字符总数时返回结果，否则说明存在循环矛盾，返回空字符串。
代码实现
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为总字符数，图中顶点与边均受固定字母表限制。- 空间复杂度：图和拓扑结构为 $O(V+E)$；Java 逐词转换字符数组另需最长单词长度的临时空间。
关键点总结
[!green]
- 相邻词的首个差异提供必要且足够的局部顺序，后续位置不能继续强加边。
- 真前缀倒置是与字母排列无关的矛盾，需要在建图时单独识别。
- 图包含全部字符，边只表示已有约束，拓扑排序为没有确定先后的字符选择一种合法顺序。
易错点总结
[!yellow]
- 对一对单词的所有不同位置都加边，会加入首差之后并不存在的约束，可能制造假环。
- 只创建出现在边中的字符，会漏掉孤立字符以及完全相同单词中的字符。
- 邻接集合已经去重，入度却重复增加，会导致删除全部边后入度仍不归零。
- 把任意包含关系当成前缀关系，判断应是从开头完整匹配到较短词结束。
- 拓扑队列为空就返回已有部分，可能忽略还被环阻塞的字符；必须核对输出总数。
- 对结果强行要求唯一固定顺序，超过了题目允许任意合法字母序的要求。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 953. 验证外星语词典 | 简单 | 原题给定字母顺序后验证词典，本题从相邻单词的第一个不同字符反推先后约束。 |
| 210. 课程表 II | 中等 | 推导字母边之后，复用拓扑排序输出一个符合依赖关系的顺序。 |
| 207. 课程表 | 中等 | 用拓扑排序处理有向依赖关系；本题从单词相邻关系提取字符先后约束，该题判断是否能移除全部节点以检测环。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！