# My Python DFS + topsort with comments

• Idea is trivial. Just build a graph using first different char in two consecutive word. Then do a DFS with topological sort. Last, combine sorted list and chars which are not in the graph but in words lists into a string.

``````class Solution(object):
def dfsHelper(self, v, color, graph, res, letterPos):
color[v] = 1
w = letterPos(letter)
if color[w] == 0 :
if self.dfsHelper(w, color, graph, res, letterPos) == False:
return False
elif color[w] == 1:
# circle detection to judge the case ["z", "a", "z"]
return False
color[v] = 2
res.append(chr(v + ord('a')))
return True

def alienOrder(self, words):
letterPos = lambda x: ord(x) - ord('a')
if words is None or len(words) == 0:
return ""
res, resUnused, graph, color = [], [], [[] for _ in range(26)], [0 for _ in range(26)]
if len(words) == 1:
return words[0]

for i in xrange(1, len(words)):
pos = 0
# find first different char
while pos < len(words[i - 1]) and pos < len(words[i]):
if words[i - 1][pos] == words[i][pos]:
pos += 1
if pos >= min(len(words[i - 1]), len(words[i])):
pos = 0
break
else:
break
if words[i - 1][pos] != words[i][pos]:
graph[letterPos(words[i - 1][pos])].append(words[i][pos])

for i in xrange(0, 26):
if graph[i] and color[i] == 0:
if self.dfsHelper(i, color, graph, res, letterPos) == False:
# use return value to quit ealier after it detects circle
return ""

# collect all unsorted chars
for i in xrange(0, len(words)):
for j in xrange(0, len(words[i])):
if color[letterPos(words[i][j])] == 0:
resUnused.append(words[i][j])
color[letterPos(words[i][j])] = 1

return "".join(res)[::-1] + "".join(resUnused)``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.