alien dictionary

🏠
 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 
14     def visit(node):
15         if node in seen:
16             return seen.get(node, False)
17         for next_node in ral[node]:
18             result = visit(next_node)
19             if not result:
20                 return False  # Cycle was detected lower down.
21         seen[node] = True
22         output["str"] += node
23         return True
24 
25     return output["str"] if all(visit(node) for node in ral) else ""
26 
27 print(alienOrder(list(sorted("some text here".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
generating callgraphs in python with mermaid