Recover an alien alphabet
A made-up language writes its words with the lowercase letters a to z, but it sorts them by its own alphabet: an order of the letters that you do not know. You get words, a list of words in that language that is meant to be in its dictionary order. The list can be broken: for some lists, no alphabet at all puts them in order.
Dictionary order compares two words letter by letter from the left. At the first position where they differ, the word whose letter comes first in the alphabet comes first. If one word ends before any difference, it is a prefix of the other, and the shorter word comes first. Equal words may sit next to each other.
Return a string that holds every letter used in words, each exactly once, in an alphabet order under which words is sorted. If several orders work, return any of them; the tests accept every one. If no order works, return the empty string "".
words = ["cat", "cab", "at", "ab", "ta", "b"]Output"catb""cab" before "at" gives c before a, "ab" before "ta" gives a before t, and "cat" before "cab" gives t before b. Together: c, a, t, b.
words = ["ba", "bc"]Output"bac"The only rule is a before c. The letter b can go anywhere, so "abc" and "acb" are accepted too.
words = ["ab", "a"]Output"""ab" sits before its own prefix "a". No alphabet puts it there.
words = ["ac", "b", "ab"]Output"""ac" before "b" says a comes before b, but "b" before "ab" says b comes before a.
1 ≤ len(words) ≤ 100
1 ≤ len(words[i]) ≤ 100
Each word uses only the lowercase letters
atoz.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.