Start learning free

LESSON 480 OF 540 · GRAPHS

Alien Dictionary in TypeScript: 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 29
    Ctrl + Enter to check

    TYPESCRIPT · GRAPHS

    Alien Dictionary in TypeScript, explained

    Problem overview

    The method alienOrder receives words, a list sorted according to an unknown alphabet. Words are compared as in any 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 comes first, so "ab" always precedes "abc".

    The method returns a string with every letter that appears in words, once each, in the order of the alien alphabet. If the list contradicts itself, so that no order of letters could make it sorted, it returns "". When several orders are possible, it returns the one that comes first alphabetically, which makes the answer unique.

    For ["wrt", "wrf", "er", "ett", "rftt"] the answer is "wertf". For ["z", "x", "z"] it is "": the first pair says z comes before x, the second says x comes before z. For ["cb", "ca"] it is "bac": the words differ at the second letter, so b comes before a, and nothing says where c goes. The orders "bac", "bca" and "cba" all work, and "bac" is first alphabetically.

    Approach: letters as a graph, then a topological order

    Each pair of neighbouring words gives at most one fact. Find the first position where the two words differ; the letter in the first word comes before the letter in the second. Everything after that position says nothing. For the first example:

    wrt wrf: t before f
wrf er: w before e
er ett: r before t
ett rftt: e before r

    Only neighbours are needed. If every word is in order with the next one, the whole list is sorted, so other pairs add nothing. That keeps the work proportional to the total number of letters, O(C), instead of comparing all pairs of words.

    Draw each fact as an arrow from one letter to the other. An alphabet that agrees with every arrow is a topological order of this graph. Kahn's algorithm builds one: count for each letter how many arrows point at it (its in-degree), place a letter whose count is 0, then lower the counts of the letters it points to, and repeat. If at some point letters are left but none has count 0, they wait on each other in a cycle and no order exists.

    To get the alphabetically first order, each round places the smallest letter that is ready. The first letter in a to z that appears in the words, isn't placed, and has no unplaced letter before it is the one to take.

    One case gives "" without any arrow: when a word is followed by a shorter word that is its own prefix, as in ["abc", "ab"], the list can't be sorted in any alphabet.

    Step by step

    1. Create waiting: 26 false values, one per letter. waiting[k] will be true while letter number k appears in the words and isn't in the answer yet. With only 26 letters, an array indexed by letter is simpler than an object.
    2. Create letters with let, starting at 0. It counts the different letters, so the answer is complete when its length reaches this number.
    3. Loop over each word with for...of.
    4. Loop over each character c of the word.
    5. Test !waiting[c.charCodeAt(0) - 97]. charCodeAt(0) gives the character's code, and a to z have the codes 97 to 122, so subtracting 97 gives an index from 0 to 25.
    6. Mark the letter by setting that entry to true.
    7. Add 1 to letters. The if ensures each letter is counted once, the first time it is met.
    8. Create graph with Array.from({length: 26}, () => []). The arrow function runs once per letter, so each letter gets its own empty array. graph[a] holds the letters that must come after a.
    9. Create inDegree: 26 zeros. inDegree[b] counts the unplaced letters that must come before b.
    10. Loop i over neighbouring pairs while i < words.length - 1.
    11. Name the pair first and second.
    12. Start j at 0 to look for the first difference.
    13. Advance while j is inside both words and first[j] === second[j]. The checks run left to right, so the characters are read only while j is inside both words.
    14. Increase j inside the loop. When it stops, either the letters at j differ or one word has run out.
    15. If j is inside both words, then first[j] and second[j] are the first letters that differ.
    16. Add the arrow: push the index of second[j] onto graph at the index of first[j].
    17. Increase inDegree at the index of second[j]. Two pairs can give the same arrow; each copy is counted here and removed once later, so that is fine.
    18. Otherwise, if first is longer than second, return "": second is a prefix of first, so it should come first in any alphabet. A first word that is shorter or equal gives no fact.
    19. Start order as an empty string.
    20. Loop while order.length < letters. Each round places one letter.
    21. Start letter at 0. It walks from a to z to find the first ready letter.
    22. Skip letters that aren't ready: while letter < 26 and !waiting[letter] || inDegree[letter] > 0, a letter is skipped. A letter is ready when it appears in the words, isn't placed, and every letter that must precede it is placed.
    23. Increase letter. The first ready letter from a to z is the smallest, which makes the answer alphabetically first.
    24. If letter === 26, no letter is ready and some are still waiting: they form a cycle. Return "".
    25. Place the letter by setting waiting[letter] to false.
    26. Append it to order with String.fromCharCode(97 + letter), which turns the index back into a character.
    27. Loop over graph[letter] with for...of, naming each nextLetter.
    28. Decrease inDegree[nextLetter]. One of the letters it waited for is placed; at 0 the next round finds it ready.
    29. Return order after the loop.

    The solution in TypeScript

    class Solution {
    alienOrder(words: string[]): string {
        const waiting: boolean[] = new Array(26).fill(false);
        let letters = 0;
        for (const word of words) {
            for (const c of word) {
                if (!waiting[c.charCodeAt(0) - 97]) {
                    waiting[c.charCodeAt(0) - 97] = true;
                    letters++;
                }
            }
        }
        const graph: number[][] = Array.from({length: 26}, () => []);
        const inDegree: number[] = new Array(26).fill(0);
        for (let i = 0; i < words.length - 1; i++) {
            const first: string = words[i];
            const second: string = words[i + 1];
            let j = 0;
            while (j < first.length && j < second.length && first[j] === second[j]) {
                j++;
            }
            if (j < first.length && j < second.length) {
                graph[first.charCodeAt(j) - 97].push(second.charCodeAt(j) - 97);
                inDegree[second.charCodeAt(j) - 97]++;
            } else if (first.length > second.length) {
                return "";
            }
        }
        let order: string = "";
        while (order.length < letters) {
            let letter = 0;
            while (letter < 26 && (!waiting[letter] || inDegree[letter] > 0)) {
                letter++;
            }
            if (letter === 26) {
                return "";
            }
            waiting[letter] = false;
            order += String.fromCharCode(97 + letter);
            for (const nextLetter of graph[letter]) {
                inDegree[nextLetter]--;
            }
        }
        return order;
    }
}

    Some TypeScript details:

    • Letters as indexes. "x".charCodeAt(0) - 97 is 23. The code is a number, so the subtraction works on numbers, and String.fromCharCode(97 + 22) gives "w".
    • for (const c of word) iterates over the characters of a string. For lowercase English letters, each is one character, so charCodeAt(0) gives its full code.
    • Array.from({length: 26}, () => []) creates 26 separate arrays. new Array(26).fill([]) would fill every slot with the same array, so an arrow pushed for one letter would show up for all of them.
    • Strings can be indexed. first[j] is a one-character string, compared with === by value. Reading past the end gives undefined, not an error, which is why the j bounds come first in the loop condition.
    • order += ... builds a new string each time, since strings are immutable. For at most 26 letters that cost doesn't matter.
    • Annotations are erased. boolean[], number[][] and : string only help the compiler.

    Complexity

    Time: O(C), where C is the total number of letters in words. Counting the letters reads each once. Each neighbouring pair is compared up to the length of the shorter word, which adds up to at most C overall. The ordering phase places at most 26 letters, and each round scans at most 26 candidates plus that letter's arrows, so it costs a constant amount of work plus the number of arrows (at most one per pair).

    Space: O(1) plus the arrows. The arrays waiting, graph and inDegree have 26 entries. The lists inside graph hold at most one arrow per neighbouring pair of words.

    Edge cases and common mistakes

    • A prefix in the wrong order. ["abc", "ab"] returns "", while ["ab", "abc"] returns "abc".
    • Contradictions. ["z", "x", "z"] returns "", and so does ["x", "y", "x"]: the arrows form a cycle, so no letter is ever ready.
    • Repeated words. ["z", "z"] returns "z". Equal neighbours give no fact, and the letter is still counted once.
    • One word. ["a"] returns "a": there are no pairs, and the only letter is placed in the first round.
    • Letters with no constraints. In ["cb", "ca"], c has no arrows. Taking the smallest ready letter each round gives "bac" rather than another valid order.
    • Forgetting letters that appear in no arrow. They still belong in the answer. That is why the letters are collected before the graph is built, and why letters is counted.
    • Comparing non-neighbours. It is unnecessary: neighbours already imply the rest. It is also slower.
    • Taking any ready letter. Any ready letter gives a valid order, but only the smallest ready one gives the alphabetically first order the statement asks for.

    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"] gives "a".
    • ["x", "y", "x"] gives "".
    Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free