这题本质上是一个拓扑排序topological sort，需要判断有没有环来处理无效input，难度主要来自这部分。Topological sort可以用dfs解决，但是没练习过还不不容易写对的。先上一个我比较满意的python解法。
class Solution:
def alienOrder(self, words: List[str]) -> str:
edges = {c: [] for word in words for c in word}
for word1, word2 in zip(words, words[1:]):
if len(word1) > len(word2) and word1.startswith(word2):
return ''
for c1, c2 in zip(word1, word2):
if c1 != c2:
edges[c1].append(c2)
break
seen = {}
order = []
def dfs(start):
if start in seen:
return seen[start]
seen[start] = False
for nxt in edges[start]:
if not dfs(nxt):
return False
order.insert(0, start)
seen[start] = True
return True
if not all(dfs(start) for start in edges):
return ''
return ''.join(order)总结一下要点。
1. edges = {c: [] for word in words for c in word} 这种一行两个循环建map的方式我也是新学的，很方便。这个map key是排前面的字母，value是排后面的字母。而且不管有没有后面的，key都加上了，这样省了另一个变量存字母表，可以对比我之前一个写对不那么好的解法。
2. 用zip遍历pair很好用，减少了出index bug的可能
3. len(word1) > len(word2) and word1.startswith(word2)，这是一个特殊的case。比如abc排在ab前面，不管什么字母表顺序，就是c排在空前面，那是无效的。
4. seen的利用，这是最巧妙的地方。写了几种尝试，发现环不太容易。如果只用一个set记录visited，就无法区分是一条已经走通的路还是当前这条路又回到某个之前经过的一点。解法方法可以用一个set记录visited，只加不减，另一个set记录当前这条路的路径，回溯时要更新，比较麻烦。这种解法利用了False和True两种states，False代表正在走的路，True代表以前已经走到底能走通的路。非常深刻，我想了很久才算大概理解。
5. if not all(dfs(start) for start in edges)，all是个我新学的function，input是collection或者更准确说是可以iterable的东西，就是要每个元素都是true就是true。换句话说就像开关串联。本来我写得是all([dfs(start) for start in edges])，后来发现代表list的方括号可以省略，估计是些语法糖。Python里面确实有很多我不知道的语法糖。
6. dfs是函数内定义的函数，可以省了self和用内函数外的变量保存状态，不用每个recursion call都pass一次。
做完这题后，重新做course schedule就容易多了。
下面是一个我之前写得比较长，很容易出bug的版本，可以对比一下。
class Solution(object):
def alienOrder(self, words):
"""
:type words: List[str]
:rtype: str
"""
if len(words) == 0:
return ''
if len(words) == 1:
return ''.join(set([c for c in words]))
edges = {}
voca = set()
for i in xrange(len(words) - 1):
for j in xrange(i + 1, len(words)):
if len(words[i]) > len(words[j]) and words[i].startswith(words[j]):
return ''
self.addEdge(words[i], words[j], edges, voca)
visited = set()
order = []
for c in voca:
# c = voca.pop()
this_visit = set()
noloop = self.dfs(c, edges, visited, this_visit, order)
if not noloop:
return ''
return ''.join(order)
def dfs(self, start, edges, visited, this_visited, order):
if start in this_visited:
return False
if start in visited:
return True
visited.add(start)
this_visited.add(start)
if start not in edges:
order.insert(0, start)
this_visited.remove(start)
return True
for nxt in edges[start]:
noloop = self.dfs(nxt, edges, visited, this_visited, order)
if not noloop:
return False
order.insert(0, start)
this_visited.remove(start)
return True
def addEdge(self, word1, word2, edges, voca):
voca.update([c for c in word1])
voca.update([c for c in word2])
for i in xrange(min(len(word1), len(word2))):
if word1[i] != word2[i]:
if word1[i] in edges:
edges[word1[i]].add(word2[i])
else:
edges[word1[i]] = set([word2[i]])
break