這題本質上是一個拓撲排序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