Start learning free

LESSON 476 OF 536 · GRAPHS

Alien Dictionary in JavaScript: 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

    JAVASCRIPT · GRAPHS

    Alien Dictionary in JavaScript, explained

    Problem overview

    The method alienOrder(words) receives an array of words that are sorted according to an unknown alphabet, which uses the lowercase English letters in some other order. It returns a string with every letter that appears in the words, each once, in the order of that alien alphabet.

    Words are compared as in any dictionary: at the first position where two words 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". If the words contradict themselves, so that no letter order can make them sorted, the method returns "". When several orders work, it returns the one that comes first in the usual alphabetical order, which makes the answer unique.

    For ["wrt", "wrf", "er", "ett", "rftt"] the answer is "wertf". Each pair of neighbouring words gives one fact: "wrt" before "wrf" says t comes before f; "wrf" before "er" says w before e; "er" before "ett" says r before t; "ett" before "rftt" says e before r. Chained together they give w, e, r, t, f. For ["z", "x", "z"] the answer is "", since z must come before x and x before z. For ["cb", "ca"] only b before a is known, and of the orders that work ("bac", "bca", "cba") the alphabetically first is "bac".

    Approach: letters as a graph, then a topological order

    Turn each fact into an arrow between two letters: an arrow from a to b means a must come before b. An order of the letters that agrees with every arrow is a topological order, and Kahn's algorithm finds one. It tracks an in-degree for each letter, the number of arrows pointing into it from letters not yet placed. A letter with in-degree 0 is ready: everything that must come before it is already in the answer. Place a ready letter, then subtract 1 from the in-degree of every letter it points to. Repeat until all letters are placed.

    Two parts of the problem need care:

    • Where the arrows come from. Only neighbouring words need to be compared. If every word is in order with the next one, the whole list is sorted, so other pairs add nothing. For a pair, find the first position where the letters differ; that gives one arrow. The letters after that position say nothing. If no position differs and the first word is longer, the second is a prefix of the first and should have come first in any alphabet: the list is contradictory.
    • Which ready letter to take. Always take the smallest one in the usual alphabet. That is what makes the answer unique.

    If at some point letters are still waiting but none has in-degree 0, each of them waits for another waiting letter. That is a cycle, so the method returns "".

    Comparing neighbouring words takes time proportional to the total number of letters, O(C). Comparing every pair of the n words would take O(n²) comparisons.

    Step by step

    1. Mark the letters that appear. waiting is an array of 26 booleans, one per letter. waiting[k] is true while letter number k appears in the words but is not in the answer yet. An array indexed by letter is simpler than an object when there are only 26 letters.
    2. Count the different letters in letters, starting at 0. The answer is complete when its length reaches this number.
    3. Loop over each word, then over each character c with for...of.
    4. Convert the letter to an index. c.charCodeAt(0) - 97 gives 0 for a, 1 for b, up to 25 for z.
    5. Mark the letter only once. If it isn't marked yet, set it to true and add 1 to letters.
    6. Build the graph. graph is 26 empty arrays, made with Array.from({length: 26}, () => []) so that each letter gets its own array. graph[a] lists the letters that must come after a.
    7. Create inDegree, 26 zeros.
    8. Loop over neighbouring pairs: i from 0 while i < words.length - 1, with first = words[i] and second = words[i + 1].
    9. Find the first difference. Start j at 0 and advance it while j is inside both words and first[j] === second[j]. The checks run left to right and stop at the first false one, so the letters are read only while j is inside both words.
    10. If j is inside both words, the letters at j are the first that differ. Push the index of second[j] onto graph at the index of first[j], and add 1 to inDegree for second[j]. Two pairs may give the same arrow; each copy is counted here and removed once later.
    11. Otherwise, if first.length > second.length, the second word is a prefix of the first: return "". A shorter or equal first word gives no fact.
    12. Collect the answer in order, an empty string, with a while loop that runs while order.length < letters. Each round places one letter.
    13. Find the smallest ready letter. Start letter at 0 and advance it while letter < 26 and the letter is not waiting or still has arrows coming in.
    14. If letter === 26, nothing is ready: return "".
    15. Place the letter. Set waiting[letter] to false and append String.fromCharCode(97 + letter) to order, which turns the index back into a character.
    16. Release the letters that follow it. For each nextLetter in graph[letter], subtract 1 from inDegree[nextLetter].
    17. Return order.

    The solution in JavaScript

    class Solution {
    alienOrder(words) {
        const waiting = 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 = Array.from({length: 26}, () => []);
        const inDegree = new Array(26).fill(0);
        for (let i = 0; i < words.length - 1; i++) {
            const first = words[i];
            const second = 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 = "";
        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;
    }
}

    JavaScript details worth knowing:

    • Character codes. "a".charCodeAt(0) is 97 and "z".charCodeAt(0) is 122. Subtracting 97 maps a letter to 0 to 25. String.fromCharCode(97 + 3) gives "d", the reverse.
    • Looping over a string. for (const c of word) gives one character at a time, as one-character strings. word[j] reads the character at an index, and past the end it gives undefined instead of an error, but the loop never gets there because of the bounds checks.
    • Array.from({length: 26}, () => []). The function runs once per index, so each entry is a different array. new Array(26).fill([]) would put the same array in all 26 entries, so pushing to one letter would change all.
    • The inner while as a search. Scanning from 0 to 26 each round costs 26 steps at most. That is why the loop picks the smallest ready letter without any sorting or priority queue.
    • Appending to a string. order += ... builds a new string each time, which is fine for at most 26 letters.

    Complexity

    Time: O(C), where C is the total number of letters in words. Marking the letters visits each one once. Comparing neighbouring words visits at most the letters of the shorter word in each pair. Placing the letters takes at most 26 rounds of at most 26 steps plus the arrows, and the number of arrows is at most the number of pairs, which is below the number of words. That part is bounded by a constant.

    Space: O(1) for the letters (arrays of 26) plus up to one arrow per neighbouring pair stored in graph.

    Edge cases and common mistakes

    • Prefix in the wrong order. ["abc", "ab"] returns "", because "ab" should come first. ["ab", "abc"] is fine and returns "abc".
    • Letters without any arrow. ["z"] returns "z", and ["z", "z"] also returns "z": equal words give no fact, and each letter appears once in the answer.
    • Letters that appear only in the rest of a word. ["ab", "adc"] returns "abcd". The only arrow is b before d, and the letters a and c have no constraints, so they are placed alphabetically when ready.
    • Cycles that come from non-neighbours. ["a", "b", "a"] returns "": the arrows a before b and b before a form a cycle.
    • Taking any ready letter. The answer must be the alphabetically first valid order. For ["za", "zb", "ca", "cb"] the arrows are z before c and a before b, and the result is "abzc". Taking letters in another order, such as z first, would give a different valid order that the lesson's tests reject.
    • Forgetting to count letters. A letter that never appears in an arrow still has to be in the answer.

    Testing

    • ["wrt", "wrf", "er", "ett", "rftt"] gives "wertf".
    • ["z", "x", "z"] gives "".
    • ["cb", "ca"] gives "bac".
    • ["abc", "ab"] gives "".
    • ["ab", "abc"] gives "abc".
    • ["ab", "adc"] gives "abcd".
    • ["za", "zb", "ca", "cb"] gives "abzc".
    Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free