Recover the Sorting Order of an Old Catalogue
Solve this ProblemA 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.
Test Case 1:
Test Case 2:
Test Case 3:
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
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Sorting Order and Test the Word List
BruteCollect the L distinct letters and generate every possible sorting order (every ordering of those letters) in dictionary order. For each sorting order, check that the word list is sorted: for each pair of neighbouring words, find the first position where they differ; the letter of the first word must come earlier in the sorting order, and if one word is a prefix of the other, the shorter one must come first. The first sorting order that passes is the lexicographically smallest, because the sorting orders are tried in dictionary order. If none passes, return the empty string. L! sorting orders make it useful only for tiny sorting orders.
O(L! · W · len)O(L)1class Solution {
2 private boolean isSorted(String[] words, int[] rank) {
3 for (int i = 0; i + 1 < words.length; i++) {
4 String a = words[i], b = words[i + 1];
5 int m = Math.min(a.length(), b.length());
6 int k = 0;
7 while (k < m && a.charAt(k) == b.charAt(k)) k++;
8 if (k == m) {
9 if (a.length() > b.length()) return false;
10 } else if (rank[a.charAt(k) - 'a'] > rank[b.charAt(k) - 'a']) {
11 return false;
12 }
13 }
14 return true;
15 }
16
17 private boolean search(String[] words, char[] letters, char[] order, int len, boolean[] used) {
18 if (len == letters.length) {
19 int[] rank = new int[26];
20 for (int i = 0; i < len; i++) rank[order[i] - 'a'] = i;
21 return isSorted(words, rank);
22 }
23 for (int i = 0; i < letters.length; i++) {
24 if (used[i]) continue;
25 used[i] = true;
26 order[len] = letters[i];
27 if (search(words, letters, order, len + 1, used)) return true;
28 used[i] = false;
29 }
30 return false;
31 }
32
33 public String sortingOrder(String[] words) {
34 boolean[] present = new boolean[26];
35 for (String w : words) {
36 for (char ch : w.toCharArray()) present[ch - 'a'] = true;
37 }
38 StringBuilder found = new StringBuilder();
39 for (int c = 0; c < 26; c++) {
40 if (present[c]) found.append((char) ('a' + c));
41 }
42 char[] letters = found.toString().toCharArray();
43 char[] order = new char[letters.length];
44 if (search(words, letters, order, 0, new boolean[letters.length])) return new String(order);
45 return "";
46 }
47}Optimal — Turn Neighbouring Words Into Rules, Then Topological Sort
OptimalEach pair of neighbouring words gives at most one rule: at the first position where they differ, the letter of the first word comes before the letter of the second one. (If there is no differing position and the first word is longer, the list is impossible.) Think of the letters as nodes and the rules as directed roads. A valid sorting order is exactly a topological order of this graph, so use Kahn's algorithm: count the rules entering each letter, repeatedly take the smallest letter with none left and release the letters it points to. If a step finds no available letter, the rules contain a cycle and the answer is the empty string.
O(W · len + L²)O(L²)1class Solution {
2 public String sortingOrder(String[] words) {
3 boolean[] present = new boolean[26];
4 for (String w : words) {
5 for (char ch : w.toCharArray()) present[ch - 'a'] = true;
6 }
7 boolean[][] edge = new boolean[26][26];
8 int[] indegree = new int[26];
9 for (int i = 0; i + 1 < words.length; i++) {
10 String a = words[i], b = words[i + 1];
11 int m = Math.min(a.length(), b.length());
12 int k = 0;
13 while (k < m && a.charAt(k) == b.charAt(k)) k++;
14 if (k == m) {
15 if (a.length() > b.length()) return "";
16 } else {
17 int x = a.charAt(k) - 'a', y = b.charAt(k) - 'a';
18 if (!edge[x][y]) {
19 edge[x][y] = true;
20 indegree[y]++;
21 }
22 }
23 }
24 int total = 0;
25 for (int c = 0; c < 26; c++) {
26 if (present[c]) total++;
27 }
28 boolean[] used = new boolean[26];
29 StringBuilder order = new StringBuilder();
30 for (int step = 0; step < total; step++) {
31 int u = -1;
32 for (int c = 0; c < 26; c++) {
33 if (present[c] && !used[c] && indegree[c] == 0) {
34 u = c;
35 break;
36 }
37 }
38 if (u == -1) return "";
39 used[u] = true;
40 order.append((char) ('a' + u));
41 for (int v = 0; v < 26; v++) {
42 if (edge[u][v]) indegree[v]--;
43 }
44 }
45 return order.toString();
46 }
47}