All problems

Alien Dictionary

Hard · topological sort

Explorers find a dictionary written in an unknown alphabet. The alphabet uses only lower-case English letters a to z, but in an order we do not know. You are given the dictionary's words, listed in sorted order according to that unknown alphabet. Words are compared the usual way: find the first position where two words differ, and the word with the earlier letter comes first; a word that is a prefix of another comes before it.

Return a string that contains each distinct letter that appears in words exactly once, written in an order of the alphabet that is consistent with the list. Letters that never appear in words are left out.

Many orders can be consistent with the same list. When more than one letter could come next, take the one that comes first in the ordinary a to z alphabet, so the answer is always the order that is smallest when compared letter by letter.

If no alphabet can produce the given list, return an empty string "". This includes a list where a word is followed by a shorter word that is its own prefix (for example "abc" and then "ab"). The same word may appear more than once in a row.

Examples

Example 1

Input: words = ["bad", "bat", "cat", "cab"]

Output: "adtbc"

The first differing letters give d before t, b before c and t before b, so d, t, b, c appear in that order. The letter a has no rule, so the smallest choice puts it first.

Example 2

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

Output: ""

"ab" is a prefix of "abc", so it would have to come first. This list cannot be sorted in any alphabet.

Example 3

Input: words = ["za", "zb", "ca", "cb"]

Output: "abzc"

The words only tell us that z comes before c and a comes before b. Of the letters free to go first (a and z) pick a, then b, then z, then c.

Constraints