Start learning free

LESSON 479 OF 539 · GRAPHS

Alien Dictionary in C#: Topological Sort with Kahn's Algorithm

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

    C# · GRAPHS

    Alien Dictionary in C#, explained

    Problem overview

    AlienOrder receives words, a list of words written with the lowercase letters but sorted in an unknown alien alphabet. It returns a string with every letter that appears in the words, once each, in the alien order. If the words contradict themselves, so that no order can make them sorted, it returns "". When several orders work, it returns the one that comes first in the usual alphabet.

    Words are compared like in a dictionary: at the first position where they differ, the word with the earlier letter comes first. If one word is a prefix of the other, the shorter one comes first, so "ab" always precedes "abc".

    For {"wrt", "wrf", "er", "ett", "rftt"} the answer is "wertf". For {"z", "x", "z"} it is "". For {"cb", "ca"} it is "bac": the words only say that b comes before a, and "bac" is the alphabetically first of the valid orders.

    Approach: turn word pairs into arrows

    Each pair of neighbouring words tells you at most one fact. Find the first position where they differ; the letter in the first word comes before the letter in the second. In the first example, "wrt" before "wrf" gives t before f, and "wrf" before "er" gives w before e. Neighbours are enough: if each word is in order with the next, the whole list is sorted.

    The facts become arrows between letters, and an order that respects every arrow is a topological order. Kahn's algorithm builds one: keep, for every letter, an in-degree, the number of arrows pointing at it from letters not yet placed. A letter with in-degree 0 is ready. Place a ready letter, then reduce the in-degree of the letters it points to.

    To get the alphabetically first answer, take the smallest ready letter in each round. If some letters remain but none is ready, they wait for each other in a cycle, and the answer is "". A second source of contradiction is a longer word before its own prefix, such as "abc" before "ab".

    Comparing every pair of words would take O(n^2) comparisons; neighbours alone give time proportional to the total number of letters.

    Step by step

    1. Mark the letters that appear. Create bool[] waiting of size 26 (one entry per letter) and an int letters that starts at 0. waiting[k] is true while letter number k appears in the words and is not in the answer yet.
    2. Scan every character with two nested foreach loops. For a letter c that is not marked, set waiting[c - 'a'] to true and add 1 to letters. A char is a number, and a to z are consecutive, so c - 'a' is 0 for a up to 25 for z.
    3. Build the graph. Create List<List<int>> graph and add 26 new empty List<int> in a loop. graph[a] holds the letters that must come after letter a.
    4. Create int[] inDegree of size 26.
    5. Go through neighbouring pairs with i from 0 while i < words.Length - 1. Name them first and second.
    6. Find the first difference. Start j at 0 and advance it while it is inside both words and first[j] == second[j].
    7. If j is inside both words, the letters at j are the first that differ. Add second[j] - 'a' to graph[first[j] - 'a'] and increase inDegree[second[j] - 'a']. Two pairs can give the same arrow; each copy is counted once here and removed once later.
    8. Otherwise, if first.Length > second.Length, second is a prefix of first yet comes after it. Return "".
    9. Run Kahn's algorithm. Create string order = "" and loop while order.Length < letters.
    10. Pick the smallest ready letter. Start letter at 0 and move it up while letter < 26 and the letter is not waiting or still has arrows coming in.
    11. Detect a cycle. If letter == 26, no letter is ready: return "".
    12. Place it. Set waiting[letter] to false and append (char) ('a' + letter) to order.
    13. Release its followers. For each nextLetter in graph[letter], decrease inDegree[nextLetter].
    14. Return order when every letter has been placed.

    The solution in C#

    class Solution {
    public string AlienOrder(string[] words) {
        bool[] waiting = new bool[26];
        int letters = 0;
        foreach (string word in words) {
            foreach (char c in word) {
                if (!waiting[c - 'a']) {
                    waiting[c - 'a'] = true;
                    letters++;
                }
            }
        }
        List<List<int>> graph = new List<List<int>>();
        for (int k = 0; k < 26; k++) {
            graph.Add(new List<int>());
        }
        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[j] == second[j]) {
                j++;
            }
            if (j < first.Length && j < second.Length) {
                graph[first[j] - 'a'].Add(second[j] - 'a');
                inDegree[second[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);
            foreach (int nextLetter in graph[letter]) {
                inDegree[nextLetter]--;
            }
        }
        return order;
    }
}

    The C# details worth knowing:

    • 'a' + letter is an int, because arithmetic on a char promotes it. Writing order += 'a' + letter would append the number as text (for letter = 3, the text 100). The cast (char) turns it back into the letter.
    • A bool[] or int[] starts with false or 0 in every slot. A List<List<int>> starts empty, and the inner lists do not exist until they are added, which is why the loop adds 26 of them.
    • foreach (char c in word) reads a string one char at a time.
    • The loop condition j < first.Length && j < second.Length && first[j] == second[j] relies on && stopping at the first false, so the indexing is safe.
    • Building order with += creates a new string each time, since strings are immutable. With at most 26 letters that cost does not matter.

    Complexity

    Time: O(C), where C is the total number of letters in words. Reading the letters and comparing neighbours is O(C). Kahn's algorithm works on at most 26 letters and at most words.Length - 1 arrows, and each round scans 26 letters at most, which is a constant.

    Space: O(n) for n words, at most. The arrays have 26 entries, and the arrow lists hold at most one entry per neighbouring pair of words.

    Edge cases and common mistakes

    • Cycle. {"z", "x", "z"} gives z before x and x before z, so the result is "".
    • Prefix after the longer word. {"abc", "ab"} returns "". The reverse, {"ab", "abc"}, is valid and gives "abc".
    • Letters with no arrows. In {"cb", "ca"} the letter c is never compared, but it must still appear in the answer. That is why the first pass records every letter, not only those in arrows.
    • Equal words. {"z", "z"} gives "z": identical neighbours say nothing.
    • Not stopping at the first difference. Only the first differing position of a pair counts. Later letters tell nothing.
    • Counting an arrow twice in the graph but once in the in-degree, or the other way round, would leave a letter that never becomes ready.
    • Lowest letter first. Taking any ready letter gives a valid order but not necessarily the alphabetically first one.

    Testing

    • {"wrt", "wrf", "er", "ett", "rftt"} gives "wertf".
    • {"z", "x", "z"} gives "".
    • {"cb", "ca"} gives "bac".
    • {"abc", "ab"} gives "".
    • {"ab", "abc"} gives "abc".
    • {"z", "z"} gives "z".
    • {"a", "b", "c"} gives "abc".
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free