火星词典 图解题解

这道题到底在问什么

示例

["wrt","wrf","er","ett","rftt"] → "wertf"

最优解：一步一步想明白

1. 3直接统计字符频率和顺序无关。
2. 4比较相邻单词第一个不同字符，得到有向边；再拓扑排序。
3. 5差异位: t < f相邻两词 wrt 和 wrf 前两位相同,第 3 位 t≠f → 字典序里 t 排在 f 前 → 连一条有向边 t→f。
4. 6差异位: w < e下一对 wrf 和 er,第 1 位就不同:w≠e → 边 w→e。每对相邻词只贡献第一个不同字符那一条边。
5. 7边: t→f · w→e · r→t · e→r再比 er/ett 得 r→t、ett/rftt 得 e→r。四条边连成一条链。入度:w=0,e/r/t/f 各=1。入度 0 的点没有任何字母必须排在它前面。
6. 8结果: w拓扑排序:w 入度 0,第一个进结果;删掉 w 的出边后,e 的入度降到 0,成为下一个候选。
7. 9结果: w e r t f沿链一路出队:w → e → r → t → f。拼起来就是这门火星语的字母表顺序 "wertf"。
8. 12一句话记住：比较相邻单词第一个不同字符，得到有向边；再拓扑排序。
9. 15环 = 矛盾约束 → 返回 ""雷区:若约束里出现环(比如又推出 e→w),说明字母顺序自相矛盾,拓扑排序会有点排不出来 → 返回空串 ""。无环才有唯一/合法顺序。
10. 22这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=graph 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。

⚠️ 容易写错的地方

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

class Solution:
    def alienOrder(self, words):
        from collections import defaultdict, deque
        graph = {ch: set() for w in words for ch in w}
        indeg = {ch: 0 for ch in graph}
        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 graph[x]:
                        graph[x].add(y)
                        indeg[y] += 1
                    break
        q = deque([ch for ch in indeg if indeg[ch] == 0])
        ans = []
        while q:
            ch = q.popleft()
            ans.append(ch)
            for nxt in graph[ch]:
                indeg[nxt] -= 1
                if indeg[nxt] == 0:
                    q.append(nxt)
        return "".join(ans) if len(ans) == len(indeg) else ""

class Solution {
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, unordered_set<char>> g;
        unordered_map<char, int> indeg;
        for (auto& w : words) for (char ch : w) indeg[ch] = 0;
        for (int i=0;i+1<words.size();i++) {
            string a = words[i], b = words[i+1];
            if (a.size() > b.size() && a.substr(0, b.size()) == b) return "";
            for (int j=0;j<min(a.size(), b.size());j++) if (a[j] != b[j]) {
                if (!g[a[j]].count(b[j])) { g[a[j]].insert(b[j]); indeg[b[j]]++; }
                break;
            }
        }
        queue<char> q;
        for (auto& [ch, deg] : indeg) if (deg == 0) q.push(ch);
        string ans;
        while (!q.empty()) {
            char ch = q.front(); q.pop(); ans += ch;
            for (char nxt : g[ch]) if (--indeg[nxt] == 0) q.push(nxt);
        }
        return ans.size() == indeg.size() ? ans : "";
    }
};

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> g = new HashMap<>();
        Map<Character, Integer> indeg = new HashMap<>();
        for (String w: words) for (char ch: w.toCharArray()) indeg.putIfAbsent(ch, 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 j=0;j<Math.min(a.length(), b.length());j++) if (a.charAt(j)!=b.charAt(j)) {
                char x=a.charAt(j), y=b.charAt(j);
                g.computeIfAbsent(x,k->new HashSet<>());
                if (g.get(x).add(y)) indeg.put(y, indeg.get(y)+1);
                break;
            }
        }
        Queue<Character> q = new ArrayDeque<>();
        for (char ch: indeg.keySet()) if (indeg.get(ch)==0) q.offer(ch);
        StringBuilder ans = new StringBuilder();
        while(!q.isEmpty()){
            char ch=q.poll(); ans.append(ch);
            for(char nxt: g.getOrDefault(ch, new HashSet<>())) if (indeg.merge(nxt,-1,Integer::sum)==0) q.offer(nxt);
        }
        return ans.length()==indeg.size()?ans.toString():"";
    }
}

# 1. 定义状态
state = init()
# 2. 按顺序读输入
for x in data:
    update(state, x)   # 只做本题允许的安全转移
# 3. 从状态里取答案
return answer(state)

// 1. init state
for (auto x : data) {
    // update state with the same invariant
}
return ans;

// 1. init state
for (int x : data) {
    // update state with the same invariant
}
return ans;

复杂度

面试官可能追问