Start learning free

LESSON 476 OF 536 · GRAPHS

Alien Dictionary in Java: Topological Sort in O(C)

Practice O(C) Read the full explanation

An alien language uses the lowercase English letters, but in an order you don't know. You are given an array of strings words from the dictionary of this language: the words are sorted in the alien alphabetical order.

Two words are compared letter by letter, as in any dictionary: at the first position where they differ, the word with the earlier letter comes first. If no position differs because one word is the beginning (a prefix) of the other, the shorter word comes first, so "ab" always comes before "abc".

Return a string with every letter that appears in words, each once, in the order of the alien alphabet. If the words contradict themselves, so that no order of the letters makes them sorted, return "" (an empty string). If several orders work, return the one that comes first in the usual alphabetical order: that makes the answer unique.

 

Example 1:

Input: words = ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"
Explanation: Each pair of neighbouring words tells us one thing, from the first letters where they differ:
    "wrt" before "wrf":  t comes before f
    "wrf" before "er":   w comes before e
    "er" before "ett":   r comes before t
    "ett" before "rftt": e comes before r
Chained together: w → e → r → t → f. These are all the letters of the words, and this is the only order that works.

Example 2:

Input: words = ["z", "x", "z"]
Output: ""
Explanation: "z" before "x" says z comes before x, but "x" before "z" says x comes before z.
The two facts form a cycle, so no order of the letters can make this list sorted.

Example 3:

Input: words = ["cb", "ca"]
Output: "bac"
Explanation: The words differ first at their second letters, so b comes before a. Nothing tells us where c goes.
The orders "bac", "bca" and "cba" all work; "bac" comes first alphabetically.

 

Constraints:

  • 1 <= words.length <= 104
  • 1 <= words[i].length <= 20
  • words[i] consists of lowercase English letters. The same word can appear more than once.

Note:

Turn the facts into arrows between letters: an order that agrees with every arrow is a topological order, which Kahn's algorithm from Course Schedule finds; taking the alphabetically smallest ready letter each time gives the answer above. Neighbouring words are enough, so the time is O(C), where C is the total number of letters in words; comparing every pair of words would take O(n2) comparisons for n words.

STEP 1 OF 31
    Ctrl + Enter to check

    JAVA · GRAPHS

    Alien Dictionary in Java, explained

    Problem overview

    An alien language uses the lowercase English letters in an unknown order. The method alienOrder receives words, a list of words from its dictionary that is sorted in the alien alphabet. Words are compared like in any dictionary: at the first position where two words differ, the word with the earlier letter comes first, and when one word is a prefix of the other the shorter word comes first. The method returns a string with every letter that appears in words, once each, in alien order. If the words contradict themselves, it returns an empty string. If several orders work, it returns the one that comes first in ordinary alphabetical order, which makes the answer unique.

    For ["wrt", "wrf", "er", "ett", "rftt"] the result is "wertf". Neighbouring words give facts: "wrt" before "wrf" means t comes before f, "wrf" before "er" means w before e, "er" before "ett" means r before t, and "ett" before "rftt" means e before r. Chained, that is w, e, r, t, f. For ["z", "x", "z"] the result is "", because z before x and x before z contradict each other. For ["cb", "ca"] the only fact is b before a, and c is unconstrained, so "bac", "bca" and "cba" all work. The alphabetically first of them, "bac", is the answer.

    The statement describes an O(C) approach, where C is the total number of letters in words. There can be up to 10,000 words of up to 20 letters.

    Approach: letters as a graph, then a topological sort

    Turn each fact into an arrow between letters: an arrow from a to b means a must come before b. An order that respects every arrow is a topological order of this graph. Kahn's algorithm builds one by repeatedly placing a letter that has no unplaced letters pointing at it, which means its in-degree is 0.

    The facts come only from neighbouring words. If every word is in order with the next one, the whole list is sorted, so comparing other pairs adds nothing, and comparing all pairs would cost O(n²) comparisons for n words. For two neighbours, find the first position where they differ. If it exists, the letter in the first word comes before the letter in the second word, and the letters after that position say nothing. If it doesn't exist, one word is a prefix of the other. That is fine when the first word is the shorter (or equal) one. When the first word is longer, the list is impossible in any alphabet, so the answer is "".

    To make the answer the alphabetically smallest order, each round of Kahn's algorithm scans from a to z and takes the first letter that is ready. A letter is ready when it appears in the words, hasn't been placed, and its in-degree is 0. If a round finds no ready letter but some letters are still waiting, they wait for each other in a cycle, and the answer is "".

    For ["cb", "ca"] there is one arrow, b to a, so a has in-degree 1. The first round skips a and takes b, which lowers the in-degree of a to 0. The next round takes a, and the last takes c. The order is "bac".

    Step by step

    1. Create waiting, a boolean array of size 26. Entry k is true while letter number k appears in the words but isn't in the answer yet. An array indexed by letter is simpler than a map for 26 letters.
    2. Create letters, an int that starts at 0 and counts the different letters.
    3. Loop over each word with a for-each loop.
    4. Loop over each char c of word.toCharArray().
    5. Check !waiting[c - 'a']: the letter hasn't been marked yet. Since a to z are consecutive, c - 'a' is 0 for a, 1 for b, up to 25 for z.
    6. Mark the letter by setting waiting[c - 'a'] to true.
    7. Count it with letters++. The if ensures each letter is counted once.
    8. Create graph as a List<List<Integer>> holding an empty ArrayList. graph.get(a) will list the letters that must come after letter a.
    9. Loop k from 0 to 25, once per letter.
    10. Add a new empty ArrayList to graph in each pass, since Java has no one-line way to build a list of separate lists.
    11. Create inDegree, an int array of size 26. inDegree[b] counts the letters that must come before b and aren't placed yet.
    12. Loop over neighbouring pairs with i < words.length - 1.
    13. Name the pair: first is words[i] and second is words[i + 1].
    14. Start j at 0 to find the first position where they differ.
    15. Advance j while it is inside both words and the characters are equal. The checks run left to right, so the characters are read only while j is valid.
    16. Increment j inside that loop.
    17. If j is inside both words, the characters at j are the first ones that differ.
    18. Add the arrow: append the index of second.charAt(j) to the list at the index of first.charAt(j).
    19. Increase inDegree at the index of second.charAt(j). Two pairs can give the same arrow, and each copy is counted here and removed once later.
    20. Otherwise, if first is longer than second, then second is a proper prefix of first yet comes after it: return "".
    21. Create order as an empty string to collect the answer.
    22. Loop while order.length() < letters. Each round places one letter.
    23. Start letter at 0.
    24. Skip letters that aren't ready: while letter < 26 and the letter isn't waiting or still has incoming arrows.
    25. Increment letter inside that loop. The first ready letter from a to z is the smallest one.
    26. If letter == 26, nothing is ready: return "".
    27. Place the letter by setting waiting[letter] to false.
    28. Append it to order with (char) ('a' + letter).
    29. Loop over the letters after it, graph.get(letter).
    30. Decrease inDegree[nextLetter]. When a count reaches 0, the next round can pick that letter.
    31. Return order.

    The solution in Java

    class Solution {
    public String alienOrder(String[] words) {
        boolean[] waiting = new boolean[26];
        int letters = 0;
        for (String word : words) {
            for (char c : word.toCharArray()) {
                if (!waiting[c - 'a']) {
                    waiting[c - 'a'] = true;
                    letters++;
                }
            }
        }
        List<List<Integer>> graph = new ArrayList<>();
        for (int k = 0; k < 26; k++) {
            graph.add(new ArrayList<>());
        }
        int[] inDegree = new int[26];
        for (int i = 0; i < words.length - 1; i++) {
            String first = words[i];
            String second = words[i + 1];
            int j = 0;
            while (j < first.length() && j < second.length() && first.charAt(j) == second.charAt(j)) {
                j++;
            }
            if (j < first.length() && j < second.length()) {
                graph.get(first.charAt(j) - 'a').add(second.charAt(j) - 'a');
                inDegree[second.charAt(j) - 'a']++;
            } else if (first.length() > second.length()) {
                return "";
            }
        }
        String order = "";
        while (order.length() < letters) {
            int letter = 0;
            while (letter < 26 && (!waiting[letter] || inDegree[letter] > 0)) {
                letter++;
            }
            if (letter == 26) {
                return "";
            }
            waiting[letter] = false;
            order += (char) ('a' + letter);
            for (int nextLetter : graph.get(letter)) {
                inDegree[nextLetter]--;
            }
        }
        return order;
    }
}

    The Java details worth a closer look:

    • Characters are numbers. A char is a 16-bit unsigned number, so c - 'a' is an int and works as an array index. This relies on the input being lowercase letters, as the constraints promise.
    • The cast on 'a' + letter. Adding an int to a char gives an int. Without (char), order += 'a' + letter would append a number such as 98 instead of the letter b.
    • Unboxing in the for-each. graph.get(letter) is a List<Integer>, and int nextLetter unboxes each element automatically.
    • Generics with the diamond. new ArrayList<>() lets the compiler infer the element type from the declaration. The lesson's editor already provides java.util. In a file of your own, add import java.util.*;.
    • String concatenation. order += ... creates a new string each time. With at most 26 letters that cost is negligible.
    • Short-circuit evaluation. In letter < 26 && (...), the array reads happen only while letter is a valid index. Without that order, waiting[26] would throw an ArrayIndexOutOfBoundsException.

    Complexity

    Reading every letter once to find the letters present, and comparing each pair of neighbours up to their first difference, takes O(C), where C is the total number of letters. There are at most 26 letters and each pair of words adds at most one arrow, so the graph work is bounded by the number of words. The placing loop runs at most 26 rounds, each scanning at most 26 letters, which is a constant. The total is O(C). The extra space is constant apart from the arrows: the arrays have 26 entries and the graph holds at most one arrow per neighbouring pair.

    Edge cases and common mistakes

    • A word followed by its own prefix. ["abc", "ab"] returns "", since the shorter word must come first. ["ab", "abc"] is fine and returns "abc".
    • Letters with no constraints. They still belong in the answer. For ["ab", "adc"] the only fact is b before d, and the result is "abcd", with a and c placed by alphabetical order.
    • A single word. The loop over pairs doesn't run, and ["abc"] returns "abc", the letters in alphabetical order.
    • Duplicate words. ["z", "z"] gives no fact and returns "z". Equal neighbours are legal.
    • Cycles. ["z", "x", "z"] and ["a", "b", "a"] both return "", because the arrows point both ways.
    • Repeated facts. Only the first differing position of a pair matters, and the same fact can appear twice. In ["ba", "bc", "ac", "cab"] the facts are a before c, b before a and a before c, and the answer is "bac".
    • Forgetting the alphabetical rule. Taking any ready letter would still give a valid order, but not necessarily the one the lesson's tests expect.

    Testing

    These results come from running the solution:

    wordsResult
    ["wrt", "wrf", "er", "ett", "rftt"]"wertf"
    ["z", "x", "z"]""
    ["cb", "ca"]"bac"
    ["abc", "ab"]""
    ["ab", "abc"]"abc"
    ["abc"]"abc"
    ["z", "z"]"z"
    ["z", "x"]"zx"
    ["ab", "adc"]"abcd"
    ["ba", "bc", "ac", "cab"]"bac"
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free