0269-alien-dictionary.py

classSolution:
defalienOrder(self, words: List[str]) ->str:
adj= {char: set() forwordinwordsforcharinword}

foriinrange(len(words) -1):
w1, w2=words[i], words[i+1]
minLen=min(len(w1), len(w2))
iflen(w1) >len(w2) andw1[:minLen] ==w2[:minLen]:
return""
forjinrange(minLen):
ifw1[j] !=w2[j]:
print(w1[j], w2[j])
adj[w1[j]].add(w2[j])
break

visited= {} # {char: bool} False visited, True current path
res= []

defdfs(char):
ifcharinvisited:
returnvisited[char]

visited[char] =True

forneighCharinadj[char]:
ifdfs(neighChar):
returnTrue

visited[char] =False
res.append(char)

forcharinadj:
ifdfs(char):
return""

res.reverse()
return"".join(res)