Given a sorted Dictionary of an Alien Language, find order of characters

The problem, simply

Aliens use our letters, but in a different order. You get their dictionary: a list of words that is already sorted in the alien order.

Work out the order of the letters. If the dictionary cannot be sorted in any order (it contradicts itself), give back an empty string. If some letters could go in more than one place, any correct order is fine.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every possible order of the letters. For each one, check whether the dictionary is sorted in that order. The first order that passes is an answer.

1. Collect the K different letters.
2. Make every ordering of them.
3. For an ordering, give each letter a rank. Walk the neighbouring word pairs and find the first spot where they differ. The top word's letter must have the smaller rank. Also, a longer word must never sit right above its own beginning.

import java.util.*;

class Solution {
    private String answer = "";

    public String findOrder(String[] words) {
        answer = "";                                   // reset between calls
        boolean[] present = new boolean[26];
        StringBuilder letters = new StringBuilder();
        for (String w : words)
            for (char ch : w.toCharArray())
                if (!present[ch - 'a']) { present[ch - 'a'] = true; letters.append(ch); }
        tryAll(letters.toString().toCharArray(), 0, words);
        return answer;
    }

    private boolean tryAll(char[] perm, int k, String[] words) {
        if (k == perm.length) {
            int[] rank = new int[26];
            for (int i = 0; i < perm.length; i++) rank[perm[i] - 'a'] = i;
            if (sorted(words, rank)) { answer = new String(perm); return true; }
            return false;
        }
        for (int i = k; i < perm.length; i++) {
            char t = perm[k]; perm[k] = perm[i]; perm[i] = t;    // pick a letter for spot k
            if (tryAll(perm, k + 1, words)) return true;
            t = perm[k]; perm[k] = perm[i]; perm[i] = t;          // undo
        }
        return false;
    }

    private boolean sorted(String[] words, int[] rank) {
        for (int i = 0; i + 1 < words.length; i++) {
            String a = words[i], b = words[i + 1];
            int n = Math.min(a.length(), b.length()), j = 0;
            while (j < n && a.charAt(j) == b.charAt(j)) j++;
            if (j == n) {
                if (a.length() > b.length()) return false;   // 'abc' above 'ab'
                continue;
            }
            if (rank[a.charAt(j) - 'a'] > rank[b.charAt(j) - 'a']) return false;
        }
        return true;
    }
}

How long it takes: there are K! orderings, and checking one reads all N words of length up to L: O(K! * N * L). With 10 letters that is already over three million orderings. Extra room: O(K) for the ordering and the recursion.

Way 2: the clever way

Do not guess. Collect the clues, then sort them.

Only neighbouring words give useful clues, and each pair gives at most one: the letters at the first spot where the two words differ. Everything after that spot tells you nothing, because the order was already decided there.

1. For each pair of neighbouring words, find the first spot where they differ. Draw an arrow from the top word's letter to the bottom word's letter.
2. If there is no differing spot and the top word is longer, the dictionary is broken: return an empty string.
3. Now you have a picture of "before" arrows. Put the letters in an order where every arrow points forward. That is a topological sort: count the arrows coming into each letter, start with the letters that have none, and rub out arrows as you go.
4. If some letters never get free, the clues make a loop: return an empty string.

import java.util.*;

class Solution {
    public String findOrder(String[] words) {
        boolean[] present = new boolean[26];
        for (String w : words)
            for (char ch : w.toCharArray()) present[ch - 'a'] = true;

        boolean[][] before = new boolean[26][26];   // before[u][v]: u comes before v
        int[] in = new int[26];                     // arrows coming into each letter
        for (int i = 0; i + 1 < words.length; i++) {
            String a = words[i], b = words[i + 1];
            int n = Math.min(a.length(), b.length()), j = 0;
            while (j < n && a.charAt(j) == b.charAt(j)) j++;
            if (j == n) {
                if (a.length() > b.length()) return "";  // a word above its own beginning
                continue;                               // a prefix gives no clue
            }
            int u = a.charAt(j) - 'a', v = b.charAt(j) - 'a';
            if (!before[u][v]) { before[u][v] = true; in[v]++; }   // count each clue once
        }

        Queue<Integer> ready = new ArrayDeque<>();
        int letters = 0;
        for (int c = 0; c < 26; c++) {
            if (!present[c]) continue;
            letters++;
            if (in[c] == 0) ready.add(c);
        }
        StringBuilder order = new StringBuilder();
        while (!ready.isEmpty()) {
            int u = ready.poll();
            order.append((char) ('a' + u));
            for (int v = 0; v < 26; v++) {
                if (before[u][v] && --in[v] == 0) ready.add(v);
            }
        }
        return order.length() == letters ? order.toString() : "";   // shorter means a loop
    }
}

How long it takes: reading the word pairs touches every letter of every word once, O(N * L). The sort looks at a K by K table of arrows, O(K^2), which is at most 26 times 26. Extra room: the table, O(K^2). With adjacency lists instead of a table you get O(N * L + K + E).

Watch out for

• The prefix case. 'abc' sitting right above 'ab' is impossible in any alphabet. Return an empty string.
• Counting the same clue twice. If two pairs both say b before a, add the arrow once, or the counts will never reach zero.
• Letters that appear in no clue. They still belong in the answer. Add every letter that appears in any word.
• Comparing words that are not neighbours. It is not wrong, but every useful clue already comes from neighbours, so it only wastes time.

What interviewers ask next

• The GeeksforGeeks version gives K and says the letters are the first K of the alphabet. Mark exactly those K letters as present and run the same code.
• Is the alien alphabet fully known? Only if the ready line never holds two letters at once. Otherwise some letters could swap.
• Can you use depth first search instead? Yes. Dive along the arrows, add each letter when it finishes, and reverse. Use a third mark for "on the current dive" to catch loops.
• Why are neighbours enough? If word 1 is above word 2 and word 2 is above word 3, the clue between 1 and 3 already follows from the other two.
• Check whether a list of words is sorted in a given alien order? That is the easy cousin: give each letter its rank and compare neighbours, O(N * L).

Remember this

Grown-up words: the letters are vertices, each clue is a directed edge, the arrows coming in are the in-degree, the line-up method is Kahn's algorithm, and the whole thing is a topological sort of a directed graph.