Letter Order From a Dictionary

Hard

Archaeologists have found a dictionary of a forgotten language. It is written in lowercase Latin letters, but the language has its own alphabet, and the order of the letters is unknown. The words in entries are sorted by that language's rules. Words compare as usual: at the first position where they differ, and if one word is the beginning of another, the shorter one comes first. Return a string with every letter that appears in the dictionary, each once, in the order of that language's alphabet. If no letter order could make the dictionary sorted, return the empty string "". It is guaranteed that whenever a suitable order exists, it is the only one.

Example 1

entries=['kot', 'kit', 'ti', 'tk'] → 'oikt'

Neighbouring pairs give: kot before kit means o comes before i, kit before ti means k before t, ti before tk means i before k. Together that leaves the single order o, i, k, t.

Example 2

entries=['ba', 'ab', 'ba'] → ''

The first pair needs b before a, the second needs a before b. No alphabet can do both.

Example 3

entries=['moon', 'mo'] → ''

mo is the beginning of moon, so under any letter order it has to come first.

Constraints

1 ≤ len(entries) ≤ 100
1 ≤ len(entries[i]) ≤ 100
entries[i] consists of lowercase Latin letters
If a suitable letter order exists, it is unique

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Graph Topological Sort Array String