剑指 Offer II 114. 外星文字典

Difficulty
Hard
Tags
图
BFS
URL
https://leetcode-cn.com/problems/Jf1JuT/
Star
现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。
给定一个字符串列表 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/

法1 BFS 拓扑排序

思路
 
题解
class Solution:
    def alienOrder(self, words: List[str]) -> str:
        # 建 图 和 入读表
        indegree = {}
        graph = {}

        for word in words:
            for char in word:
                indegree[char] = 0
                graph[char] = []

        for i in range(0, len(words)-1):
            # 排除掉极端例子 比如 abd， ab显然是不合适的
            if len(words[i]) > len(words[i+1]) and words[i][0:len(words[i+1])] == words[i+1]:
                return ""
            length = min(len(words[i]), len(words[i+1]))
            for j in range(length):
                if words[i][j] != words[i+1][j]:
                    graph[words[i][j]].append(words[i+1][j])
                    indegree[words[i+1][j]] += 1
                    break
        # 找入口
        queue = []
        for key, val in indegree.items():
            if val == 0:
                queue.append(key)
    
        # 拓扑排序
        res = ""
        while queue:
            cur = queue.pop(0)
            res += cur
            for temp in graph[cur]:
                indegree[temp] -= 1
                if indegree[temp] == 0:
                    queue.append(temp)


        return res if len(res) == len(indegree) else ""