# Python DFS, BFS, toposort solutions

• DFS:

``````    import collections

self.greater = collections.defaultdict(set)

for i in range(len(words)-1):
minlen = min(len(words[i]), len(words[i+1]))
j=0
while j < minlen and words[i][j] == words[i+1][j]:
j+=1
if j < minlen:

charset = set(''.join(words))

self.mark = {}

self.orderlist = collections.deque()

for i in charset:
if i not in self.mark:
if not self.visit(i):
return ""

return "".join(self.orderlist)

def visit(self, i):

if i in self.mark and self.mark[i] == 2:
return False
elif i in self.mark and self.mark[i] == 1:
return True

if i not in self.mark:
self.mark[i] = 2

for j in self.greater[i]:
if not self.visit(j):
return False

self.mark[i] = 1

self.orderlist.appendleft(i)

return True
``````

BFS:

``````    import collections

que = collections.deque()

less = collections.defaultdict(set)
greater = collections.defaultdict(set)

for i in range(len(words)-1):
minlen = min(len(words[i]), len(words[i+1]))
j=0
while j < minlen and words[i][j] == words[i+1][j]:
j+=1
if j < minlen:
que.append([words[i][j],words[i+1][j]])

charset = set(''.join(words))

subset = [x for x in charset if x not in greater]

while que:
[k,l] = que.popleft()
if l in less:
for m in less[l]:
if m == k:
return ""
elif k not in greater[m]:
que.append([k,m])

return ''.join(subset)+''.join(w[0] for w in sorted(greater.items(), key=lambda x: len(x[1])))
``````

Toposort:

``````    import collections

less = collections.defaultdict(set)
greater = collections.defaultdict(set)

for i in range(len(words)-1):
minlen = min(len(words[i]), len(words[i+1]))
j=0
while j < minlen and words[i][j] == words[i+1][j]:
j+=1
if j < minlen:

charset = set(''.join(words))

orderlist = []

deque = collections.deque([x for x in charset if x not in greater])

while deque:
i = deque.popleft()
if i in less:
for j in less[i]:
greater[j].remove(i)
if len(greater[j]) == 0:
del greater[j]
deque.append(j)
orderlist.append(i)

if len(greater) > 0:
return ""
else:
return "".join(orderlist)``````

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