alien dictionary

← 🏠

 1def 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
27print(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