1.題目基本信息
1.1.題目描述
現有一種使用英語字母的外星文語言，這門語言的字母順序與英語順序不同。
給定一個字符串列表 words ，作為這門語言的詞典，words 中的字符串已經 按這門新語言的字母順序進行了排序 。
請你根據該詞典還原出此語言中已知的字母順序，并 按字母遞增順序 排列。若不存在合法字母順序，返回 "" 。若存在多種可能的合法字母順序，返回其中 任意一種 順序即可。
字符串 s 字典順序小于 字符串 t 有兩種情況：
-
在第一個不同字母處，如果 s 中的字母在這門外星語言的字母順序中位于 t 中字母之前，那么 s 的字典順序小于 t 。
-
如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 時，s 的字典順序也小于 t 。
1.2.題目地址
https://leetcode.cn/problems/alien-dictionary/description/
2.解題方法
2.1.解題思路
kahn算法 / DFS
2.2.解題步驟
kahn算法進行拓撲排序步驟
-
第一步，根據"有序"的words數組構建各個字符之間的有向圖，使用鄰接表進行存儲；并在建圖的過程中統計各個結點的入度信息到inDegree哈希表中
-
1.1.將所有字符都初始化到圖中，并初始化它們入度為0
-
1.2.遍歷相鄰單詞組，構建圖，并填充入度到inDegree哈希表
-
1.2.1.將邊添加到圖中
-
1.2.2.統計入度
-
1.2.3.word1和word2的前綴相同且word1的長度大于word2的長度是不合法的情況，直接返回空字符串
-
-
-
第二步，kahn算法進行拓撲排序。先判斷圖中是否有環，如果無環，返回任意一個拓撲排序的序列，如果有環，返回空字符串
-
2.1.將入度為0的結點添加到隊列中，并初始化拓撲排序序列數組
-
2.2.kahn算法進行拓撲排序
-
-
第三步，如果inDegree中所有結點的入度都為0，說明無環
DFS算法步驟
-
第一步，構建出現的字母集合
-
第二步，構建有向圖的鄰接表和入度字典
-
第三步，DFS進行拓撲排序
3.解題代碼
kahn算法版本代碼
from collections import defaultdict, dequeclass Solution:def alienOrder(self, words: List[str]) -> str:# 思路：拓撲排序# 第一步，根據"有序"的words數組構建各個字符之間的有向圖，使用鄰接表進行存儲；并在建圖的過程中統計各個結點的入度信息到inDegree哈希表中graph = defaultdict(list)inDegree = defaultdict(int)# 1.1.將所有字符都初始化到圖中，并初始化它們入度為0charsSet = set()for w in words:for c in w:charsSet.add(c)for c in charsSet:graph[c] = []inDegree[c] = 0# 1.2.遍歷相鄰單詞組，構建圖，并填充入度到inDegree哈希表n = len(words)for i in range(1, n):word1, word2 = words[i - 1], words[i]j = 0length1, length2 = len(word1), len(word2)while j < min(length1, length2):if word1[j] != word2[j]:# 1.2.1.將邊添加到圖中graph[word1[j]].append(word2[j])# 1.2.2.統計入度inDegree[word2[j]] += 1breakj += 1# 1.2.3.word1和word2的前綴相同且word1的長度大于word2的長度是不合法的情況，直接返回空字符串if j == min(length1, length2) and length1 > length2:return ""# print(graph)# print(inDegree)# 第二步，kahn算法進行拓撲排序。先判斷圖中是否有環，如果無環，返回任意一個拓撲排序的序列，如果有環，返回空字符串# 2.1.將入度為0的結點添加到隊列中，并初始化拓撲排序序列數組arr = [] # 拓撲排序的序列que = deque()for node in graph.keys():if inDegree[node] == 0:que.append(node)arr.append(node)# 2.2.kahn算法進行拓撲排序while que:for _ in range(len(que)):node = que.popleft()del inDegree[node]for neighNode in graph[node]:inDegree[neighNode] -= 1if inDegree[neighNode] == 0:que.append(neighNode)arr.append(neighNode)# print(inDegree, arr)# 第三步，如果inDegree中所有結點的入度都為0，說明無環result = "".join(arr) if len(inDegree) == 0 else ""return result
dfs算法版本代碼
from collections import defaultdict, dequeclass Solution:# 思路一：DFSdef alienOrder(self, words: List[str]) -> str:length=len(words)# 構建出現的字母集合lettersSet=set()for word in words:for letter in word:lettersSet.add(letter)# 構建圖、入度字典graph={letter:[] for letter in lettersSet}inDict=defaultdict(int)for i in range(1,length):preWord=words[i-1]word=words[i]isNormalEnd=Truefor preLetter,letter in zip(preWord,word):# print(preLetter,letter)if preLetter!=letter:graph[preLetter].append(letter)inDict[letter]+=1isNormalEnd=Falsebreakif isNormalEnd:# print("t4",preWord,word)if len(preWord)>len(word):return ""# print("t1",graph,inDict,lettersSet)# dfsvisiting=set()visited=set()stack=[]# 返回True代表無環def dfs(node):if node in visited:return Trueif node in visiting:return Falsevisiting.add(node)for subNode in graph[node]:noCircle=dfs(subNode)if not noCircle:return Falsevisiting.remove(node)visited.add(node)stack.append(node)return Truefor node in list(graph.keys()):noCircle=dfs(node)if not noCircle:return ""return "".join(stack[::-1])
4.執行結果
