题目

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

假设，您并不知道其中字母之间的先后顺序。但是，会收到词典中获得一个 不为空的 单词列表。因为是从词典中获得的，所以该单词列表内的单词已经 按这门新语言的字母顺序进行了排序。

您需要根据这个输入的列表，还原出此语言中已知的字母顺序。

示例 1：
输入:
[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
输出: "wertf"

示例 2：
输入:
[
"z",
"x"
]
输出: "zx"

示例 3：
输入:
[
"z",
"x",
"z"
]
输出: ""
解释: 此顺序是非法的，因此返回 ""。

提示：

  • 你可以默认输入的全部都是小写字母
  • 若给定的顺序是不合法的，则返回空字符串即可

  • 若存在多种可能的合法字母顺序，请返回其中任意一种顺序即可

    方案（Kahn算法）

    1. class Solution:
    2.   def alienOrder(self, words: List[str]) -> str:
    3.       # 使用邻接表构建图, 和入度
    4.       adj = collections.defaultdict(collections.OrderedDict)
    5.       inDegree = {}
    6.       for word in words:
    7.           for w in word:
    8.               inDegree[w] = 0
    10.       def addAdj(a, b):  # 在图中 a -> b
    11.           if b not in adj[a]:
    12.               inDegree[b] += 1
    13.               adj[a][b] = True
    15.       # 将词典中字符串的字符两两对比，只有第一个不同的字符才是正确的排序，如ert和wrf，只能推断出e的优先级高于w，剩余字符的优先级不能推断。
    16.       for i in range(len(words) - 1):
    17.           j = 0
    18.           while True:  # 相邻的单词两两比较
    19.               if j >= len(words[i]):
    20.                   break
    21.               if j >= len(words[i+1]): # 用例 ["abc", "ab"] 应为 ""
    22.                   return ""
    24.               if words[i][j] == words[i+1][j]:
    25.                   j += 1
    26.                   continue
    27.               addAdj(words[i][j], words[i+1][j])
    28.               break
    30.       # Kahn 算法
    31.       order = []
    32.       # 起点
    33.       deque = collections.deque([k for k, v in inDegree.items() if v == 0])
    35.       while deque:
    36.           node = deque.popleft()  # 弹出出度为 0 的节点
    37.           order.append(node)
    38.           # 将该节点指向的节点入度 -1, 如果得到的入度 == 0 则加入 deque
    39.           for nextNode, _ in adj[node].items():
    40.               inDegree[nextNode] -= 1
    41.               if inDegree[nextNode] == 0:
    42.                   deque.append(nextNode)
    44.       # 如果最后入度中仍然有不为 0 的，则说明有环
    45.       for _, v in inDegree.items():
    46.           if v != 0:
    47.               return ""
    48.       return "".join(order)

  • 注意第 23 行，用例 ["abc", "ab"] 应返回 “”

  • 注意题目理解，即第 17 行。

    原文

    https://leetcode-cn.com/explore/interview/card/2020-top-interview-questions/288/graph/1289/
    https://leetcode-cn.com/problems/alien-dictionary/solution/java-tuo-bu-pai-xu-by-zxy0917/