LeetCode 269. 火星词典

2025-03-03 HGNULB 约 11 分钟

文章信息 8 个分类 7 个标签

分类

题目描述

✅ 269. 火星词典

题意分析

给定一批由小写字母组成的单词，它们已经按照某种未知的字母表顺序排成了升序。要反推出这套字母表的一个合法顺序并返回；如果输入本身自相矛盾，返回空字符串；如果存在多个合法顺序，返回任意一个即可。

「已按新字典序升序排列」是全部信息的来源。字典序比较的规则决定了信息量非常有限：两个单词一旦在某个位置分出高下，后面的字符就完全不再参与比较。因此每一对相邻单词最多只能贡献一条「某字符排在某字符之前」的结论，多提取一条都是凭空捏造。

「返回任意一个」这句话说明答案通常不唯一，只要与所有已知约束相容即可，不需要追求字典序最小或其他附加性质。

非法输入有两种形态，必须分开处理。一种是环：约束互相矛盾，比如同时要求 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 114. 火星词典	困难	与本题同题，可用来专门复练字符注册与前缀矛盾这两个细节
LCR 115. 序列重建	中等	与 444 同题，考察点集中在唯一性判定而非合法性判定
面试题 04.01. 节点间通路	中等	只判断两点是否连通，一次搜索即可，不涉及入度与顺序输出