```
"""
The idea is to contruct a directed graph from all possible orderings of input characters,
then get the topological order if it's a DAG. Return '' if there is a cycle.
If any character's topological order cannot be determined, simply append it to the result.
Example case:
["zyx", "zx"]
where 'z' is not in the DAG, we should add it to the topological order ['y','x']
"""
from collections import defaultdict
NEVER, ONPATH, DONE = 0, 1, 2 # visiting status for DFS
class Solution(object):
def alienOrder(self, words):
"""
:type words: List[str]
:rtype: str
"""
# get all possible edges to construct DAG
adj = defaultdict(set)
char_set = set(words[-1])
for i in range(len(words)-1):
char_set.update(words[i])
for c1, c2 in zip(words[i], words[i+1]):
if c1 != c2:
adj[c1].add(c2)
break
# try to get the topological order of the DAG
# also pass the overall character set to add to result if necessary
return self.topo_sort(adj, char_set)
def topo_sort(self, adj, cset):
visit = defaultdict(int)
tp_order = []
for u in adj.keys():
if not visit[u] and self.hasCycle(adj, u, visit, tp_order, cset):
return ''
return ''.join(tp_order[::-1] + list(cset))
def hasCycle(self, adj, u, visit, tp_order, cset):
if visit[u] == DONE:
return False
visit[u] = ONPATH
for v in adj[u]:
if visit[v] == ONPATH or self.hasCycle(adj, v, visit, tp_order, cset):
return True
tp_order.append(u)
cset.remove(u)
visit[u] = DONE
return False
```