Alien Alphabet (Topological Sort)
hardpy_datastructuresRecover an alphabet from a list of words sorted in an unknown order (the
"alien dictionary" problem). Implement two functions; get_alphabet (given) ties
them together.
build_graph(words)→{letter: set of letters that come strictly after it}. Every letter that appears is a key. For each adjacent pair of words, the first position where they differ yields one constraint: the earlier word's letter comes before the later word's letter.extract_alphabet(graph)→ a list of all letters in one order consistent with every constraint (a topological sort).
graphlib is not allowed — implement the sort yourself. Inputs must not change.
Constraints
- no graphlib
Your solution
Edit get_alphabet and run the real pytest suite in your browser — no install required. Your code is saved locally.
Loading the Python runtime (first run only)…
Hints
Hint 1
build_graph: every letter is a node; for each adjacent word pair, the first differing position gives one edge (earlier letter -> later letter).
Hint 2
extract_alphabet: topological sort (Kahn's algorithm) — repeatedly take a node with no remaining incoming edges.