269. Alien Dictionary
这道题最最最难点是看出这题是topology sort的解法，如果看出是拓扑排序的话，那么题目就简单多了。
class Solution(object):
def alienOrder(self, words):
"""
:type words: List[str]
:rtype: str
"""
# topology sort
# 首先第一步要构建graph
# 找出链表中的顺序
s = set()
for word in words:
for c in word:
s.add(c)
graph = {c:set() for c in s} # char to set()
degree = {c:0 for c in s} # char to int
# 处理词之间的关系,依据链表的顺序
for i in range(1, len(words)):
self.cal(words[i-1], words[i], graph)
# 构造degree
for key in graph:
for val in graph[key]:
degree[val] = degree[val] + 1
# 找出入度为0的加入queue
queue = []
for key in degree:
if degree[key] == 0:
queue.append(key)
if not queue:
return ""
# print graph, degree
res = ""
while queue:
key = queue.pop(0)
res += key
for val in graph[key]:
degree[val] -= 1
if degree[val] == 0:
queue.append(val)
for key, val in degree.iteritems():
if val != 0:
return ""
return res
def cal(self, w1, w2, graph):
for i in range(min(len(w1), len(w2))):
if w1[i] != w2[i]:
graph[w1[i]].add(w2[i])
break
