LeetCode 269困难高级图

火星词典图解题解

Q: 为什么用拓扑排序而不是直接排字母？

我们只知道部分两两先后（偏序），不是全部字母都两两可比。拓扑排序正是把偏序补成一个相容的全序。

Q: 怎么判断输入自相矛盾（无解）？

建图后若图里有环，拓扑就排不出全部字母——出队字母数小于总字母数时返回空串。

这道题到底在问什么

相邻两个单词，从左往右找到第一个不同的字母 c1、c2——既然 c1 所在的词排在前面，就说明在这门语言里 c1 < c2。把所有这样的「先后关系」收集起来，求一个满足全部关系的字母全序。

输入: words = ["wrt","wrf","er","ett","rftt"]
输出: "wertf"

最优解：一步一步想明白

3记住这一句：相邻差异 = 有向边，拓扑排序 = 字母全序。下面一步步建图再排序。
4先把出现过的 5 个字母 w、e、r、t、f 摆成节点，入度都标 0。接下来逐对相邻单词比较，连出有向边。
5比较 "wrt" 和 "wrf"：逐位对齐，第 3 位首次不同——'t'（在前面的词里）对上 'f'。高亮这两个字母。
6'wrt' 排在 'wrf' 前面 → 在这门语言里 t < f。连有向边 t→f，'f' 的入度 +1（看它上方）。
7比较 "wrf" 和 "er"：逐位对齐，第 1 位首次不同——'w'（在前面的词里）对上 'e'。高亮这两个字母。
8'wrf' 排在 'er' 前面 → 在这门语言里 w < e。连有向边 w→e，'e' 的入度 +1（看它上方）。
9比较 "er" 和 "ett"：逐位对齐，第 2 位首次不同——'r'（在前面的词里）对上 't'。高亮这两个字母。
10'er' 排在 'ett' 前面 → 在这门语言里 r < t。连有向边 r→t，'t' 的入度 +1（看它上方）。
11比较 "ett" 和 "rftt"：逐位对齐，第 1 位首次不同——'e'（在前面的词里）对上 'r'。高亮这两个字母。
12'ett' 排在 'rftt' 前面 → 在这门语言里 e < r。连有向边 e→r，'r' 的入度 +1（看它上方）。
13建图完成（w→e、e→r、r→t、t→f）。开始 Kahn 拓扑排序：看节点上方入度，'w' 的入度为 0（没有字母必须排在它前面）→ 入队。
14队首 'w' 出队，确定它是当前最靠前的字母，追加到结果："w"。接着删掉它的所有出边。
15删除出边 w→e：'e' 的入度减 1，变为 0——降到 0，马上可以入队。
16'e' 的入度已为 0（没有任何字母必须排在它前面）→ 入队，等待定序。
17队首 'e' 出队，确定它是当前最靠前的字母，追加到结果："we"。接着删掉它的所有出边。
18删除出边 e→r：'r' 的入度减 1，变为 0——降到 0，马上可以入队。
19'r' 的入度已为 0（没有任何字母必须排在它前面）→ 入队，等待定序。
20队首 'r' 出队，确定它是当前最靠前的字母，追加到结果："wer"。接着删掉它的所有出边。
21删除出边 r→t：'t' 的入度减 1，变为 0——降到 0，马上可以入队。
22't' 的入度已为 0（没有任何字母必须排在它前面）→ 入队，等待定序。
23队首 't' 出队，确定它是当前最靠前的字母，追加到结果："wert"。接着删掉它的所有出边。
24删除出边 t→f：'f' 的入度减 1，变为 0——降到 0，马上可以入队。
25'f' 的入度已为 0（没有任何字母必须排在它前面）→ 入队，等待定序。
26队首 'f' 出队，追加到结果。所有 5 个字母都出队、入度全清零——拓扑排序完成！字母全序就是出队顺序 "wertf"，这就是这门火星语言的字典序。

⚠️ 容易写错的地方

✗ 错：只比对一对就停

✓ 对：所有相邻单词都要比，但每对只取第一个不同字母

第一个不同字母之后的位无法推断先后

✗ 错：漏掉前缀非法情形

✓ 对：若长词在前、短词在后且长词以短词开头（如 "abc" 在 "ab" 前）直接返回空

这违反字典序，本身是矛盾输入

✗ 错：有环不返回空

✓ 对：拓扑排出的字母数 < 总字母数 → 存在环 → 返回 ""

环代表相互矛盾的先后关系，无解

完整代码（Python / C++ / Java）

Python

def alienOrder(words):
    g = {c: set() for w in words for c in w}
    indeg = {c: 0 for c in g}
    for a, b in zip(words, words[1:]):
        if len(a) > len(b) and a.startswith(b):
            return ""           # 非法：前缀反序
        for x, y in zip(a, b):
            if x != y:
                if y not in g[x]:
                    g[x].add(y); indeg[y] += 1
                break
    q = deque([c for c in g if indeg[c] == 0])
    out = []
    while q:
        c = q.popleft(); out.append(c)
        for nb in g[c]:
            indeg[nb] -= 1
            if indeg[nb] == 0: q.append(nb)
    return "".join(out) if len(out) == len(g) else ""

C++

string alienOrder(vector<string>& words){
    unordered_map<char, unordered_set<char>> g;
    unordered_map<char,int> indeg;
    for(auto& w: words) for(char c: w){ g[c]; indeg[c]; }
    for(int i=0;i+1<words.size();++i){
        string& a=words[i]; string& b=words[i+1];
        if(a.size()>b.size() && a.substr(0,b.size())==b) return "";
        for(int k=0;k<min(a.size(),b.size());++k){
            if(a[k]!=b[k]){
                if(!g[a[k]].count(b[k])){ g[a[k]].insert(b[k]); indeg[b[k]]++; }
                break;
            }
        }
    }
    queue<char> q;
    for(auto& p: indeg) if(p.second==0) q.push(p.first);
    string out;
    while(!q.empty()){
        char c=q.front(); q.pop(); out+=c;
        for(char nb: g[c]) if(--indeg[nb]==0) q.push(nb);
    }
    return out.size()==g.size()? out : "";
}

Java

public String alienOrder(String[] words) {
    Map<Character, Set<Character>> g = new HashMap<>();
    Map<Character, Integer> indeg = new HashMap<>();
    for (String w : words) for (char c : w.toCharArray()) {
        g.putIfAbsent(c, new HashSet<>());
        indeg.putIfAbsent(c, 0);
    }
    for (int i = 0; i + 1 < words.length; i++) {
        String a = words[i], b = words[i + 1];
        if (a.length() > b.length() && a.startsWith(b)) return "";
        for (int k = 0; k < Math.min(a.length(), b.length()); k++) {
            char x = a.charAt(k), y = b.charAt(k);
            if (x != y) {
                if (g.get(x).add(y)) indeg.put(y, indeg.get(y) + 1);
                break;
            }
        }
    }
    Queue<Character> q = new LinkedList<>();
    for (char c : indeg.keySet()) if (indeg.get(c) == 0) q.offer(c);
    StringBuilder sb = new StringBuilder();
    while (!q.isEmpty()) {
        char c = q.poll(); sb.append(c);
        for (char nb : g.get(c)) {
            indeg.put(nb, indeg.get(nb) - 1);
            if (indeg.get(nb) == 0) q.offer(nb);
        }
    }
    return sb.length() == g.size() ? sb.toString() : "";
}

复杂度

时间

O(C + ΣL)

ΣL=所有单词总长度（建图），C=不同字母数（拓扑）

空间

O(C + E)

邻接表存边 + 入度表 + 队列

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着火星词典的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

为什么用拓扑排序而不是直接排字母？+

我们只知道部分两两先后（偏序），不是全部字母都两两可比。拓扑排序正是把偏序补成一个相容的全序。

怎么判断输入自相矛盾（无解）？+

建图后若图里有环，拓扑就排不出全部字母——出队字母数小于总字母数时返回空串。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把火星词典一步步讲透（全站已上线 905 份讲透，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

了解年卡方案 →先去动画页看完整样板 →

把这道题真正拿下

看动画图解 →火星词典交互动画,逐步看清每一步怎么走

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 269困难高级图

火星词典图解题解

这道题到底在问什么

输入: words = ["wrt","wrf","er","ett","rftt"]
输出: "wertf"

最优解：一步一步想明白

3记住这一句：相邻差异 = 有向边，拓扑排序 = 字母全序。下面一步步建图再排序。
4先把出现过的 5 个字母 w、e、r、t、f 摆成节点，入度都标 0。接下来逐对相邻单词比较，连出有向边。
5比较 "wrt" 和 "wrf"：逐位对齐，第 3 位首次不同——'t'（在前面的词里）对上 'f'。高亮这两个字母。
6'wrt' 排在 'wrf' 前面 → 在这门语言里 t < f。连有向边 t→f，'f' 的入度 +1（看它上方）。
7比较 "wrf" 和 "er"：逐位对齐，第 1 位首次不同——'w'（在前面的词里）对上 'e'。高亮这两个字母。
8'wrf' 排在 'er' 前面 → 在这门语言里 w < e。连有向边 w→e，'e' 的入度 +1（看它上方）。
9比较 "er" 和 "ett"：逐位对齐，第 2 位首次不同——'r'（在前面的词里）对上 't'。高亮这两个字母。
10'er' 排在 'ett' 前面 → 在这门语言里 r < t。连有向边 r→t，'t' 的入度 +1（看它上方）。
11比较 "ett" 和 "rftt"：逐位对齐，第 1 位首次不同——'e'（在前面的词里）对上 'r'。高亮这两个字母。
12'ett' 排在 'rftt' 前面 → 在这门语言里 e < r。连有向边 e→r，'r' 的入度 +1（看它上方）。
13建图完成（w→e、e→r、r→t、t→f）。开始 Kahn 拓扑排序：看节点上方入度，'w' 的入度为 0（没有字母必须排在它前面）→ 入队。
14队首 'w' 出队，确定它是当前最靠前的字母，追加到结果："w"。接着删掉它的所有出边。
15删除出边 w→e：'e' 的入度减 1，变为 0——降到 0，马上可以入队。
16'e' 的入度已为 0（没有任何字母必须排在它前面）→ 入队，等待定序。
17队首 'e' 出队，确定它是当前最靠前的字母，追加到结果："we"。接着删掉它的所有出边。
18删除出边 e→r：'r' 的入度减 1，变为 0——降到 0，马上可以入队。
19'r' 的入度已为 0（没有任何字母必须排在它前面）→ 入队，等待定序。
20队首 'r' 出队，确定它是当前最靠前的字母，追加到结果："wer"。接着删掉它的所有出边。
21删除出边 r→t：'t' 的入度减 1，变为 0——降到 0，马上可以入队。
22't' 的入度已为 0（没有任何字母必须排在它前面）→ 入队，等待定序。
23队首 't' 出队，确定它是当前最靠前的字母，追加到结果："wert"。接着删掉它的所有出边。
24删除出边 t→f：'f' 的入度减 1，变为 0——降到 0，马上可以入队。
25'f' 的入度已为 0（没有任何字母必须排在它前面）→ 入队，等待定序。
26队首 'f' 出队，追加到结果。所有 5 个字母都出队、入度全清零——拓扑排序完成！字母全序就是出队顺序 "wertf"，这就是这门火星语言的字典序。

⚠️ 容易写错的地方

✗ 错：只比对一对就停

✓ 对：所有相邻单词都要比，但每对只取第一个不同字母

第一个不同字母之后的位无法推断先后

✗ 错：漏掉前缀非法情形

✓ 对：若长词在前、短词在后且长词以短词开头（如 "abc" 在 "ab" 前）直接返回空

这违反字典序，本身是矛盾输入

✗ 错：有环不返回空

✓ 对：拓扑排出的字母数 < 总字母数 → 存在环 → 返回 ""

环代表相互矛盾的先后关系，无解

完整代码（Python / C++ / Java）

Python

def alienOrder(words):
    g = {c: set() for w in words for c in w}
    indeg = {c: 0 for c in g}
    for a, b in zip(words, words[1:]):
        if len(a) > len(b) and a.startswith(b):
            return ""           # 非法：前缀反序
        for x, y in zip(a, b):
            if x != y:
                if y not in g[x]:
                    g[x].add(y); indeg[y] += 1
                break
    q = deque([c for c in g if indeg[c] == 0])
    out = []
    while q:
        c = q.popleft(); out.append(c)
        for nb in g[c]:
            indeg[nb] -= 1
            if indeg[nb] == 0: q.append(nb)
    return "".join(out) if len(out) == len(g) else ""

C++

string alienOrder(vector<string>& words){
    unordered_map<char, unordered_set<char>> g;
    unordered_map<char,int> indeg;
    for(auto& w: words) for(char c: w){ g[c]; indeg[c]; }
    for(int i=0;i+1<words.size();++i){
        string& a=words[i]; string& b=words[i+1];
        if(a.size()>b.size() && a.substr(0,b.size())==b) return "";
        for(int k=0;k<min(a.size(),b.size());++k){
            if(a[k]!=b[k]){
                if(!g[a[k]].count(b[k])){ g[a[k]].insert(b[k]); indeg[b[k]]++; }
                break;
            }
        }
    }
    queue<char> q;
    for(auto& p: indeg) if(p.second==0) q.push(p.first);
    string out;
    while(!q.empty()){
        char c=q.front(); q.pop(); out+=c;
        for(char nb: g[c]) if(--indeg[nb]==0) q.push(nb);
    }
    return out.size()==g.size()? out : "";
}

Java

public String alienOrder(String[] words) {
    Map<Character, Set<Character>> g = new HashMap<>();
    Map<Character, Integer> indeg = new HashMap<>();
    for (String w : words) for (char c : w.toCharArray()) {
        g.putIfAbsent(c, new HashSet<>());
        indeg.putIfAbsent(c, 0);
    }
    for (int i = 0; i + 1 < words.length; i++) {
        String a = words[i], b = words[i + 1];
        if (a.length() > b.length() && a.startsWith(b)) return "";
        for (int k = 0; k < Math.min(a.length(), b.length()); k++) {
            char x = a.charAt(k), y = b.charAt(k);
            if (x != y) {
                if (g.get(x).add(y)) indeg.put(y, indeg.get(y) + 1);
                break;
            }
        }
    }
    Queue<Character> q = new LinkedList<>();
    for (char c : indeg.keySet()) if (indeg.get(c) == 0) q.offer(c);
    StringBuilder sb = new StringBuilder();
    while (!q.isEmpty()) {
        char c = q.poll(); sb.append(c);
        for (char nb : g.get(c)) {
            indeg.put(nb, indeg.get(nb) - 1);
            if (indeg.get(nb) == 0) q.offer(nb);
        }
    }
    return sb.length() == g.size() ? sb.toString() : "";
}

复杂度

时间

O(C + ΣL)

ΣL=所有单词总长度（建图），C=不同字母数（拓扑）

空间

O(C + E)

邻接表存边 + 入度表 + 队列

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着火星词典的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

为什么用拓扑排序而不是直接排字母？+

我们只知道部分两两先后（偏序），不是全部字母都两两可比。拓扑排序正是把偏序补成一个相容的全序。

怎么判断输入自相矛盾（无解）？+

建图后若图里有环，拓扑就排不出全部字母——出队字母数小于总字母数时返回空串。

想听吴师兄把这道题讲给你听？

了解年卡方案 →先去动画页看完整样板 →

把这道题真正拿下

看动画图解 →火星词典交互动画,逐步看清每一步怎么走

火星词典 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

火星词典 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

火星词典图解题解

火星词典图解题解