火星词典

Submission

运行时间: 26 ms

内存: 16.1 MB

from collections import defaultdict, deque
from typing import List


class Solution:
    def alienOrder(self, words: List[str]) -> str:
        graph = defaultdict(set)
        charset = set(words[0])
        n = len(words)

        for i in range(1, n):
            prv, nxt = words[i - 1], words[i]
            charset.update(nxt)
            if nxt.startswith(prv):
                continue
            elif prv.startswith(nxt):
                return ''
            k = 0
            while k < min(len(prv), len(nxt)):
                if prv[k] != nxt[k]:
                    graph[prv[k]].add(nxt[k])
                    break
                k += 1

        ind = {ch: 0 for ch in charset}
        res = []
        for node, children in graph.items():
            for chd in children:
                ind[chd] += 1

        q = deque([ch for ch, ch_ind in ind.items() if ch_ind == 0])
        while q:
            p = q.popleft()
            res.append(p)
            for chd in graph[p]:
                ind[chd] -= 1
                if ind[chd] == 0:
                    q.append(chd)

        return ''.join(res) if len(res) == len(charset) else ''

Explain

该题解利用拓扑排序的方法来确定火星字典中字符的顺序。首先，建立一个字符间的依赖图，即从一个单词到下一个单词比较不同字符的位置，形成有向边。使用一个入度表来记录每个字符的入度。然后，使用一个队列实现广度优先搜索（BFS），将入度为0的字符依次加入队列。每次从队列中取出一个字符，表示这个字符在字典顺序中的下一个位置，然后减少其相邻节点的入度，并检查新的入度为0的节点加入队列。这个过程持续到队列为空。如果最终结果的长度等于字符集大小，表示找到了有效的顺序；如果不是，则可能存在环，表示没有有效的字符顺序。

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

空间复杂度: O(V + E)

from collections import defaultdict, deque
from typing import List


class Solution:
    def alienOrder(self, words: List[str]) -> str:
        graph = defaultdict(set)  # 创建一个图，其中每个节点指向一个字符集
        charset = set(words[0])  # 初始化字符集合
        n = len(words)  # 单词数量

        for i in range(1, n):
            prv, nxt = words[i - 1], words[i]  # 比较相邻两个单词
            charset.update(nxt)  # 更新字符集
            if nxt.startswith(prv):
                continue  # 如果nxt以prv开始，无需添加新边
            elif prv.startswith(nxt):
                return ''  # 如果prv以nxt开始，存在矛盾，直接返回空字符串
            k = 0
            while k < min(len(prv), len(nxt)):
                if prv[k] != nxt[k]:
                    graph[prv[k]].add(nxt[k])  # 建立依赖关系
                    break
                k += 1

        ind = {ch: 0 for ch in charset}  # 初始化每个字符的入度
        res = []
        for node, children in graph.items():
            for chd in children:
                ind[chd] += 1  # 更新入度

        q = deque([ch for ch, ch_ind in ind.items() if ch_ind == 0])  # 入度为0的节点入队列
        while q:
            p = q.popleft()
            res.append(p)  # 添加到结果中
            for chd in graph[p]:
                ind[chd] -= 1  # 减少入度
                if ind[chd] == 0:
                    q.append(chd)  # 入度为0，加入队列

        return ''.join(res) if len(res) == len(charset) else ''  # 检查是否所有字符都被排序了

Explore

在构建依赖图时，只有当第一个不同的字符出现时，才添加有向边。这种方法确保了只有在两个字符之间存在明显的顺序关系时，才会形成依赖关系。通过对相邻单词进行逐字符比较，并在发现第一个不同的字符时停止比较，可以避免错误的依赖关系。这样做不仅提高了算法的效率，还避免了因错误单词顺序（例如字典序错误的输入）而造成的不必要的依赖关系。

如果一个单词是另一个单词的前缀，并且前者出现在后者之后，这在语言的字典排序中通常表示一个冲突或错误，因为较短的单词应该先出现。这种情况下直接返回空字符串是因为这反映了单词列表中潜在的逻辑错误或输入错误，导致无法构建有效的字符顺序。继续构建可能会忽略这种根本的错误，导致生成的字符顺序不符合实际的字典序规则。

在拓扑排序的实现中，环的检测是通过检查最终排序结果的长度是否等于图中节点的总数来间接实现的。如果存在环，则图中至少有一部分节点的入度永远不会变为0，因此这些节点不会被加入结果序列中，导致最终结果的长度小于节点总数。如果长度等于节点总数，则表明没有环，所有节点都被正确排序。

结果字符串的长度与字符集大小不相等通常发生在存在环的情况下。如果图中存在环，则环内的节点因为相互依赖，其入度不可能变为0，这些节点就不会被加入到结果字符串中。此外，如果输入数据或构建图的逻辑有误，也可能导致无法将所有字符正确排序。这些情况下，结果字符串的长度会小于字符集的大小，表明排序失败。