269. Alien Dictionary
這道題最最最難點(diǎn)是看出這題是topology sort的解法圾另，如果看出是拓?fù)渑判虻脑捹搜敲搭}目就簡(jiǎn)單多了诸衔。
class Solution(object):
def alienOrder(self, words):
"""
:type words: List[str]
:rtype: str
"""
# topology sort
# 首先第一步要構(gòu)建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
# 處理詞之間的關(guān)系,依據(jù)鏈表的順序
for i in range(1, len(words)):
self.cal(words[i-1], words[i], graph)
# 構(gòu)造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
