#24HardGraph & Topological Sort· Kahn's Algorithm with a Min-Heap

Alien Dictionary

An alien language uses a subset of the lowercase English letters, but in an unknown alphabetical order. You receive `words`, a list of words from its dictionary, claimed to be sorted lexicographically according to the alien order. Lexicographic order works as usual: compare two words letter by letter; the first position where they differ decides, and if one word is a prefix of the other, the shorter word comes first. Return a string containing every distinct letter that appears in `words`, arranged in an alien order under which `words` really is sorted. If several orders work, return the one that is smallest in ordinary English alphabetical comparison (so letters with no constraint between them appear in a-z order). If no order works, return an empty string `""`.

Input format

words: array of lowercase strings

Output format

String: the letters in a valid alien order (smallest such string), or `""`

Examples

Input: words = ["wrt", "wrf", "er", "ett", "rftt"]

Output: "wertf"

The pairs give t < f, w < e, r < t and e < r, which force the single order w, e, r, t, f.

Input: words = ["z", "x", "z"]

Output: ""

z < x and x < z form a cycle, so no order exists.

Input: words = ["ab", "adc"]

Output: "abcd"

The only rule is b < d; a and c are unconstrained, so the smallest valid string is abcd.

Constraints

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of lowercase English letters.

Study first

Stacks, Queues & Monotonic Sequences

#graphs
#topological-sort
#strings
#heap