火星词典

难度: Hard

现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。

给定一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。

请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回 "" 。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。

字符串 s 字典顺序小于 字符串 t 有两种情况：

在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。

示例 1：

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

示例 2：

输入：words = ["z","x"]
输出："zx"

示例 3：

输入：words = ["z","x","z"]
输出：""
解释：不存在合法字母顺序，因此返回 "" 。

提示：

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 仅由小写英文字母组成

注意：本题与主站 269 题相同： https://leetcode-cn.com/problems/alien-dictionary/

Submission

运行时间: 28 ms

内存: 16.0 MB

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        edge, s = defaultdict(list), set()
        for word in words:
            s.update(set(word)) # 统计全部字符
        indegree = [0] * 26 # 使用的都是英文字母！
        pre = words[0]
        for i in range(1, len(words)):
            now = words[i] 
            for sa, sb in zip(pre, now):
                if sa != sb:
                    edge[sa].append(sb) # 统计出度的边
                    indegree[ord(sb) - ord('a')] += 1 # 统计入度
                    break
            else: # for循环没有发生break或者continue时，迭代完成后要执行的操作可在else下声明
                if len(pre) > len(now):
                    return ""
            pre = now
        order = [e for e in s if indegree[ord(e) - ord('a')] == 0] # 从入度为0开始
        for sa in order:
            for sb in edge[sa]:
                indegree[sc := ord(sb) - ord('a')] -= 1 # 海象运算符可以在运算过程中赋值！
                if not indegree[sc]: # 入度至多有一次为0！
                    order.append(sb) # 随着循环的进行order自动延长，直至遍历完！
        return "".join(order) if len(order) == len(s) else ""

Explain

这道题解的思路基于图论中的拓扑排序。首先，题解尝试通过给定的单词列表构建一个有向图，其中节点代表字母，有向边代表字母间的顺序关系。使用边和入度数组来建立这个图的结构。接下来，题解遍历单词列表，比较相邻的单词，找到第一个不同的字母对，以此来确定字母间的顺序关系，即在图中添加边。特别的，如果发现短单词排在长单词后面，那么立即返回空字符串，因为这是不合法的。最后，题解使用拓扑排序算法来得到一个有效的字母顺序。如果排序过程中某个时刻没有入度为0的字母而图中仍有字母未处理，则说明存在环，也返回空字符串。

时间复杂度: O(n + V + E)

空间复杂度: O(26) 或 O(1)

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        edge, s = defaultdict(list), set()
        for word in words:
            s.update(set(word)) # 统计全部字符
        indegree = [0] * 26 # 初始化入度数组
        pre = words[0]
        for i in range(1, len(words)):
            now = words[i]
            for sa, sb in zip(pre, now):
                if sa != sb:
                    edge[sa].append(sb) # 建立从sa到sb的边
                    indegree[ord(sb) - ord('a')] += 1 # 增加sb的入度
                    break
            else: # 处理长度不一致的特殊情况
                if len(pre) > len(now):
                    return ""
            pre = now
        order = [e for e in s if indegree[ord(e) - ord('a')] == 0] # 入度为0的节点作为起始点
        for sa in order:
            for sb in edge[sa]:
                indegree[sc := ord(sb) - ord('a')] -= 1 # 处理sa的每一个邻接点sb
                if not indegree[sc]: # 如果sb的入度为0，加入队列
                    order.append(sb)
        return "".join(order) if len(order) == len(s) else "" # 如果排序完成的长度与节点数相同，返回结果，否则返回空字符串

Explore

在构建有向图时，如果遇到两个单词完全相同，例如`aa`和`aa`，代码中通过`zip(pre, now)`比较相邻单词中的每个字母。由于两个单词相同，`zip`函数会比较每个位置的字母，但都是相同的，因此不会进入`if sa != sb`的逻辑块内，也就不会在图中添加任何新的边。这种情况不会影响图的构建，因为没有新的顺序关系被发现，也不会影响最终的结果，因为字母的相对顺序并没有改变。

如果较短的单词排在较长的单词之后，例如`abc`之后是`ab`，这在字母顺序的逻辑上是不合法的。因为按照字典顺序的规则，如果一个单词的前缀与另一个单词相同，那么较短的单词应该排在前面。在这种情况下，`ab`不能排在`abc`之后，因为这意味着`c`需要在`b`之前出现，同时又在`b`之后出现，这自然形成了一个逻辑上的矛盾。因此，这种情况下一定不存在合法的字母顺序，所以返回空字符串。

在构建图和处理入度数组时，我们只增加不同字母对中后一个字母的入度，因为这反映了前一个字母应该在后一个字母之前出现的顺序关系。如果我们增加两个字母的入度，这将意味着两个字母都依赖于对方，形成了一个循环依赖，这在拓扑排序中是没有意义的。正确的做法是只表达一种单向依赖关系。这样的处理确保了拓扑排序能够正确地表示字母之间的顺序，如果存在一种合法的顺序。如果处理错误，可能会导致无法解析出一个有效的顺序，或者错误地认为存在依赖环。