现有一种使用字母的全新语言，这门语言的字母顺序与英语顺序不同。假设，您并不知道其中字母之间的先后顺序。但是，会收到词典中获得一个 不为空的 单词列表。因为是从词典中获得的，所以该单词列表内的单词已经 按这门新语言的字母顺序进行排序。您需要根据这个输入的列表，还原出此语言中已知的字母顺序。
例如：
输入：
[ "wrt", "wrf", "er", "ett", "rftt" ]
输出：
正确的顺序是：“wertf”
解题：意思是按照单词的顺序排序了。比如wrt和wrf，wrt排在wrf前面，说明优先级t>f，依次类推则有：
t->f
w->e
r->t
e->r
最终则有顺序：wertf
比较麻烦的就是如何转换成字符间的顺序格式，之后用拓扑排序就好了。
class Solution: def alienOrder(self,words): #chars用于获取字母集合 chars=set(''.join(words)) print(chars) #用于存储入度 degrees={x:0 for x in chars} from collections import defaultdict #用于存储优先级 graph=defaultdict(list) #pair是从上到下两两匹对 for pair in zip(words,words[1:]): print(pair) #x,y依次取出匹对的字母 for x,y in zip(*pair): print(x,y) if x!=y: #建立优先级关系 graph[x].append(y) #入度增加1 degrees[y]+=1 break print(degrees) print(graph) queue=[] for i in chars: if degrees[i] == 0: queue.append(i) res="" while queue: x=queue.pop(0) res+=x for i in graph[x]: degrees[i]-=1 if degrees[i]==0: queue.append(i) return res*(set(res)==chars) s=Solution() print(s.alienOrder([ "wrt", "wrf", "er", "ett", "rftt" ]))
结果：
第二种方法：使用深度优先遍历
class Solution: def alienOrder(self,words): #chars用于获取字母集合 chars=set(''.join(words)) print(chars) #用于存储入度 degrees={x:0 for x in chars} from collections import defaultdict #用于存储优先级 graph=defaultdict(list) #pair是从上到下两两匹对 for pair in zip(words,words[1:]): print(pair) #x,y依次取出匹对的字母 for x,y in zip(*pair): print(x,y) if x!=y: #建立优先级关系 graph[x].append(y) #入度增加1 degrees[y]+=1 break print(degrees) print(graph) lis=[] for i in chars: if degrees[i] == 0: lis.append(i) res="" while lis: tmp=[] for ch in lis: res+=ch for c in graph[ch]: degrees[c]-=1 if degrees[c]==0: tmp.append(c) del graph[ch] lis=tmp return res if len(res)==len(chars) else "" s=Solution() print(s.alienOrder([ "wrt", "wrf", "er", "ett", "rftt" ]))
参考：https://www.jianshu.com/p/ee280c838f2d