Recover the Sorting Order of an Old Catalogue
Implement sortingOrder
A librarian finds an old catalogue whose entries are sorted by a lost rule: some order of the letters, different from the usual one. From the list of entries, work out that order of the letters (the sorting order). If several sorting orders fit the list, return the lexicographically smallest one, and return an empty string when no sorting order can produce this list.
Comparing neighbouring words gives rules of the form "this letter comes before that letter". The rules form a directed graph, and a topological order of the letters is a sorting order.
Example 1:
Input: words = ["dd","db","be","bea","ea","ac"]
Output: "cdbea"
Example 2:
Input: words = ["abc","ab"]
Output: ""
Example 3:
Input: words = ["ba","bb","ab","ba"]
Output: ""
+ 15 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ words.length ≤ 8; each word has 1 to 5 letters from a to h; the words use at most 8 distinct letters - ●
The words are listed in the order given by an unknown sorting order of the letters (that order is what we want to recover) - ●
In dictionary order a word comes before any longer word that starts with it; two equal words may appear next to each other - ●
Return a sorting order (a string with each letter that appears in the words exactly once) that makes the list sorted; when several sorting orders work, return the lexicographically smallest one. Return "" if no sorting order can make the list sorted
words =