Uber Phone Screen Alien Dictionary：验证词序再推导字母序

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 验证版输入为单词列表及包含所有用到字符的无重复 order，判断整个列表是否按该字母序非递减排列；空词合法。
• 推断版输入为已宣称按某未知字母序排序的单词列表，只对出现过的字符输出一种合法顺序；若证据矛盾返回空串。若多个顺序可行，训练实现选字典序最小者。
• 题目只给 LC953/LC269 题号；字符集、大小写、空词及并列解取法均是本篇训练约定，不声称面试官规定。

解题路线

1. 验证版预处理字符 rank，逐对比较相邻单词。扫描共同前缀后，第一处不同字符决定先后；若完全相同到较短词结束，则长词在前是非法的。相邻对都合法即可利用排序关系的传递性保证整个序列合法。
2. 推断版先把所有出现过的字符建为节点。对每对相邻词只取首个不同字符 a/b，添加约束 a→b；同一条边重复出现时不能重复增加 b 的入度。若左词是右词的真扩展却排在前面，直接判无解。
3. 对约束图做 Kahn 拓扑排序；用最小堆取当前零入度字符可稳定得到字典序最小的有效序。处理节点数少于字符数意味着有向环，返回无解。
4. 只比较相邻词已足够：若每一对都满足同一个字母序，传递性保证任意更远词也有序；在推断版中，任何合法字母序都必须满足这些相邻差异约束。

手动走一遍

验证版 words=["hello","leetcode"]、order="hlabcdefgijkmnopqrstuvwxyz" 时，首个差异 h/l 的顺序合法。推断版 ["wrt","wrf","er","ett","rftt"] 给出 t→f、w→e、r→t、e→r，因此一种答案是 "wertf"。["abc","ab"] 是前缀冲突；["z","x","z"] 形成环。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Two distinct Alien Dictionary tasks: check a given order and infer one."""

import heapq


def is_sorted(words: list[str], order: str) -> bool:
    if len(set(order)) != len(order):
        raise ValueError("order contains duplicate characters")
    rank = {char: i for i, char in enumerate(order)}
    if any(char not in rank for word in words for char in word):
        raise ValueError("word uses character absent from order")

    for left, right in zip(words, words[1:]):
        for a, b in zip(left, right):
            if a != b:
                if rank[a] > rank[b]:
                    return False
                break
        else:
            if len(left) > len(right):
                return False
    return True


def infer_order(words: list[str]) -> str:
    chars = set("".join(words))
    graph = {char: set() for char in chars}
    indegree = {char: 0 for char in chars}

    for left, right in zip(words, words[1:]):
        for a, b in zip(left, right):
            if a != b:
                if b not in graph[a]:
                    graph[a].add(b)
                    indegree[b] += 1
                break
        else:
            if len(left) > len(right):
                return ""

    ready = [char for char in chars if indegree[char] == 0]
    heapq.heapify(ready)
    answer = []
    while ready:
        char = heapq.heappop(ready)
        answer.append(char)
        for next_char in graph[char]:
            indegree[next_char] -= 1
            if indegree[next_char] == 0:
                heapq.heappush(ready, next_char)
    return "".join(answer) if len(answer) == len(chars) else ""

复杂度

设全部词字符数为 T，不同字符数为 V，约束边数为 E。验证版建 rank 并比较相邻词最多 O(T+|order|) 时间、O(|order|) 空间；推断版生成约束 O(T)，小顶堆拓扑 O((V+E)log V)，图和入度占 O(V+E)。

易错点与追问

容易失分的边界

• 只处理第一处不同字符，不能把同一对词后续不同位置也加入图，否则推导出不存在的约束。
• 漏掉 ["abc","ab"] 的非法前缀；仅靠建边不会发现这个矛盾。
• 重复边多次增加入度，导致零入度队列无法释放节点。
• 图中环表示证据自相矛盾，不能返回一个只有部分字符的拓扑前缀。

继续深挖

• 若要求判定字母序是否唯一，拓扑过程中何时能观察到多个可选零入度节点？
• 若 order 只覆盖词中部分字符，验证版应报输入错误还是将未知字符排到最后？先定义接口。
• 若增量追加新词，如何维护约束图并检测新环，而不每次完全重建？