alien dictionary

Go Back home
 1 def alienOrder(words):
 2     ral = {c : [] for word in words for c in word}
 3     for first_word, second_word in zip(words, words[1:]):
 4         for c, d in zip(first_word, second_word):
 5             if c != d: 
 6                 ral[d].append(c)
 7                 break
 8         else:
 9             if len(second_word) < len(first_word): 
10                 return ""
11 
12     seen, output = {}, {'str':''}
13     def visit(node):
14         if node in seen:
15             return seen.get(node, False)
16         for next_node in ral[node]:
17             result = visit(next_node)
18             if not result:
19                 return False # Cycle was detected lower down.
20         seen[node] = True
21         output['str'] += node
22         return True
23 
24     return output['str'] if all(visit(node) for node in ral) else ""
25 
26 print(alienOrder(list(sorted('desmond had a barrow in the market place molie was a singer in a band desmond said to mollie girl i like your face and then he went took her by hand oladi oblada life goes on brah ah ha how the life goes on allie hello blood sugar sucker fish in my dish how many pieces do you wish step into a heaven where i feel it on the soul side god please me be my soul bride every woman has a piece of aphrodite copulate to create a sense of sexual lite kissing her virginity my affinity i mingle with the gods i mingle with divinity hill lea leo lie lil'.split()))))
graph TD h --> f l --> h n --> l p --> n b --> a r --> n e --> a l --> e r --> l i --> a y --> r c --> b r --> o d --> c i --> e v --> s o --> i e --> d f --> e e --> a i --> e g --> f o --> i e --> d h --> g n --> d s --> n e --> a l --> a r --> l i --> e o --> i i --> h t --> n k --> i l --> k o --> a i --> e f --> e k --> f l --> k t --> l m --> l r --> n e --> a i --> e o --> i l --> i y --> o o --> m f --> b l --> f n --> l p --> o l --> i e --> a s --> p e --> a x --> n i --> e n --> d o --> i t --> o u --> t g --> c t --> s o --> h v --> t w --> v e --> a h --> e i --> h t --> s o --> i y --> w

See Also:

accounts merge
shifted zip