Recover the alien alphabet

Question

You are given a list of words that are sorted in lexicographic order according to some unknown alphabet. Derive a possible ordering of the distinct letters. If the input is self-contradictory, return "".

words = ["wrt", "wrf", "er", "ett", "rftt"]   ->   "wertf"

Return any valid letter order, or "" if none exists. Aim for $O(C)$ where $C$ is the total number of characters.

Accepted Answer

Each adjacent pair of words reveals one ordering fact: scan them together and the first position where they differ tells you that the earlier word's letter precedes the later word's letter. That single edge per pair builds a dependency graph over letters, and a valid alphabet is any topological order of it. Two failure modes: a cycle among the letters (contradictory clues), and a prefix violation where a longer word sits before its own prefix (like "abc" before "ab"), which no ordering can justify. Tracing the example: wrt vs wrf gives t - f; wrf vs er gives w - e; er vs ett gives r - t; ett …

Recover the alien alphabet

Your answer

More Coding questions